<html>
<head>
<title>C++ Annotations Version 6.5.0</title>
</head>
<body text="black" bgcolor="white">
<hr>
<ul>
    <li> <a href="cplusplus.html">Table of Contents</a>
    <li> <a href="cplusplus18.html">Previous Chapter</a>
    <li> <a href="cplusplus20.html">Next Chapter</a>
</ul>
<hr>
<a name="TEMPCLASS"></a><a name="l336"></a>
<h1>Chapter 19: Template classes</h1>
<a name="templateclasses"></a>
<blockquote>
    <em>
        Don't hesitate to send in feedback: send an e-mail if you like the
        C++ Annotations; if you think that important material was omitted;
        if you find errors or typos in the text or the code examples;
        or if you just feel like e-mailing. Send your e-mail to
        <a href="mailto:f.b.brokken@rug.nl">Frank B. Brokken</a>.
<p>
<strong>Please</strong> state the document version you're referring to, as found in
        the title (in this document: 6.5.0) and please state chapter and
        paragraph name or number you're referring to.
<p>
All received mail is processed conscientiously, and received
        suggestions for improvements will usually have been processed by the
        time a new version of the Annotations is released. Except for the
        incidental case I will normally not acknowledge the receipt of
        suggestions for improvements. Please don't interpret this as me not
        appreciating your efforts.
    </em>
</blockquote>
<p>
<a name="templateclasses/intro"></a>    Like function templates, templates can be constructed for complete
classes. A <a name="an2618"></a>
template class can be considered when the class should be able
to handle different types of data. Template classes are frequently used in
<strong>C++</strong>: chapter <a href="cplusplus12.html#Containers">12</a> covered general data structures like
<code>vector, stack</code> and <code>queue</code>, defined as <em>template classes</em>. With
template classes, the <a name="an2619"></a>
 algorithms and the data on which the
algorithms operate are completely separated from each other. To use a
particular <a name="an2620"></a>
data structure, operating on a particular data type, only the
<a name="an2621"></a>
data type needs to be specified when the template class object is defined
or declared, e.g., <code>stack&lt;int&gt; iStack</code>.
<p>
Below the construction of template classes is discussed. In a sense, template
classes compete with
        <a name="an2622"></a>
object oriented programming
    (cf. chapter <a href="cplusplus14.html#POLYMORPHISM">14</a>), where a mechanism somewhat similar to
templates is seen. Polymorphism
        <a name="an2623"></a>

    allows the programmer to postpone the definitions of algorithms, by
deriving classes from a <a name="an2624"></a>
base class in which the algorithm is only partially
implemented, while the data upon which the algorithms operate may first be
defined in <a name="an2625"></a>
derived classes, together with member functions that were
defined as
    <a name="an2626"></a>
pure virtual functions in the base class to handle the data. On the
other hand, templates allow the programmer to postpone the specification of
the data upon which the algorithms operate. This is most clearly seen with the
abstract containers, completely specifying the algorithms but at the same time
leaving the data type on which the algorithms operate completely
unspecified. 
<p>
The correspondence between template classes and polymorphic classes is
well-known. In their book <strong>C++ Coding Standards</strong> (Addison-Wesley, 2005)
    <a name="an2627"></a>
<a name="an2628"></a>

    Sutter and Alexandrescu (2005) refer to 
    <a name="an2629"></a>
<em>static polymorphism</em><a name="an2630"></a>
 and
    <a name="an2631"></a>
<a name="an2632"></a>
<em>dynamic polymorphism</em>. <em>Dynamic</em>
polymorphism is what we use when overriding virtual members: Using the
<a name="an2633"></a>
<em>vtable</em> construction the function that's actually called depends on the
type of object a (base) class pointer points to. <em>Static</em> polymorphism is
used when templates are used: depending on the actual types, the compiler
<em>creates</em> the code, compile time, that's appropriate for those particular
types. There's no need to consider static and dynamic polymorphism as mutually
exlusive variants of polymorphism. Rather, both can be used together,
combining their strengths. A warning is in place, though. When a template
class defines virtual members <em>all</em> virtual members are instantiated for
every instantiated type. This has to happen, since the compiler must be able
to construct the class's <code>vtable</code>.
<p>
Generally, template classes are easier to use. It is certainly easier to write
<code>stack&lt;int&gt; istack</code> to create a stack of <code>ints</code> than to derive a new
class <code>Istack: public stack</code> and to implement all necessary member functions
to be able to create a similar stack of <code>ints</code> using object oriented
programming. On the other hand, for each different type that is used with a
template class the complete class is reinstantiated, whereas in the context of
object oriented programming the derived classes <em>use</em>, rather than <em>copy</em>,
the functions that are already available in the base class (but see also
section <a href="cplusplus19.html#DERIVEDTEMPCLASS">19.9</a>).
<p>
<a name="TEMPCLASSDEF"></a><a name="l337"></a>
<h2>19.1: Defining template classes</h2>
<a name="templateclasses/definitions"></a>    Now that we've covered the construction of template functions, we're ready
for the next step: constructing template classes. Many useful template classes
already exist. Instead of illustrating how an existing template class was
constructed, let's discuss the construction of a useful new template class.
<p>
In chapter <a href="cplusplus17.html#STL">17</a> we've encountered the <code>auto_ptr</code> class (section
<a href="cplusplus17.html#AUTOPTR">17.3</a>). The <code>auto_ptr</code>, also called <a name="an2634"></a>
<em>smart pointer</em>, allows us to
define an object, acting like a pointer. Using <code>auto_ptr</code>s rather than plain
pointers we not only ensure proper memory management, but we may also prevent
memory leaks when objects of classes using pointer data-members cannot
completely be constructed.
<p>
The one disadvantage of <a name="an2635"></a>
 <code>auto_ptr</code>s is that
they can only be used for single objects and not for pointers to
arrays of objects. Here we'll construct the template class <code>FBB::auto_ptr</code>,
behaving like <code>auto_ptr</code>, but managing a pointer to an array of objects.
<p>
Using an existing class as our point of departure also shows an important
design principle: it's often easier to construct a template (function or
        <a name="an2636"></a>

        <a name="an2637"></a>
 class) from an existing template than
to construct the template completely from scratch. In this case the existing
<code>std::auto_ptr</code> acts as our model.  Therefore, we want to provide the class
with the following members:
    <ul>
    <li> Constructors to create an object of the class <code>FBB::auto_ptr</code>;
    <li> A <a name="an2638"></a>
destructor;
    <li> An overloaded <a name="an2639"></a>
<code>operator=()</code>;
    <li> An <a name="an2640"></a>
<code>operator[]()</code> to retrieve and reassign the elements given
their indices.
    <li> All other members of <code>std::auto_ptr</code>, with the exception of
the dereference operator (<a name="an2641"></a>
<code>operator*()</code>), since our <code>FBB::auto_ptr</code> object
will hold multiple objects, and although it would be entirely possible to
define it as a member returning a reference to the first element of its array
of objects, the member <code>operator+(int index)</code>, returning the address of
object <code>index</code> would most likely be expected too. These extensions of
<code>FBB::auto_ptr</code> are left as exercises to the reader.
    </ul>
    Now that we have decided which members we need, the class interface can be
constructed. Like template functions, a template class definition begins with
the keyword <a name="an2642"></a>
<code>template</code>, which is also followed by a non-empty list of
template type
        <a name="an2643"></a>

    and/or non-type parameters, surrounded by angle brackets. The
<code>template</code> keyword followed by the template parameter list enclosed in
angle brackets is called a <a name="an2644"></a>
<em>template announcement</em> in the <strong>C++</strong>
Annotations. In some cases the template announcement's parameter list may be
empty, leaving only the angle brackets.
<p>
Following the template announcement the class interface is provided, in
which the formal template type parameter names may be used to represent types
and constants. The class interface is constructed as usual. It starts with the
keyword <code>class</code> and ends with a semicolon.
<p>
Normal <a name="an2645"></a>
design considerations should be followed when constructing
template class member functions or template class constructors:
        <a name="an2646"></a>

    template class type parameters
        <a name="an2647"></a>

    should preferably be defined as <code>Type const &amp;</code>, rather than <code>Type</code>, to
prevent unnecessary copying of large <a name="an2648"></a>
data structures. Template
        <a name="an2649"></a>

    class constructors should use <a name="an2650"></a>
member initializers rather than member
assignment within the body of the constructors, again to prevent double
assignment of composed objects: once by the default constructor of the object,
once by the assignment itself.
<p>
Here is our initial version of the class
        <a name="an2651"></a>
<code>FBB::auto_ptr</code>
        <a name="an2652"></a>

    showing all its members:
        <pre>
    namespace FBB
    {
        template &lt;typename Data&gt;
        class auto_ptr
        {
            Data *d_data;

            public:
                auto_ptr();
                auto_ptr(auto_ptr&lt;Data&gt; &amp;other);
                auto_ptr(Data *data);
                ~auto_ptr();
                auto_ptr&lt;Data&gt; &amp;operator=(auto_ptr&lt;Data&gt; &amp;rvalue);
                Data &amp;operator[](size_t index);
                Data const &amp;operator[](size_t index) const;
                Data *get();
                Data const *get() const;
                Data *release();
                void reset(Data *p = 0);
            private:
                void destroy();
                void copy(auto_ptr&lt;Data&gt; &amp;other);
                Data &amp;element(size_t idx) const;
        };

        template &lt;typename Data&gt;
        inline auto_ptr&lt;Data&gt;::auto_ptr()
        :
            d_data(0)
        {}

        template &lt;typename Data&gt;
        inline auto_ptr&lt;Data&gt;::auto_ptr(auto_ptr&lt;Data&gt; &amp;other)
        {
            copy(other);
        }

        template &lt;typename Data&gt;
        inline auto_ptr&lt;Data&gt;::auto_ptr(Data *data)
        :
            d_data(data)
        {}

        template &lt;typename Data&gt;
        inline auto_ptr&lt;Data&gt;::~auto_ptr()
        {
            destroy();
        }

        template &lt;typename Data&gt;
        inline Data &amp;auto_ptr&lt;Data&gt;::operator[](size_t index)
        {
            return d_data[index];
        }

        template &lt;typename Data&gt;
        inline Data const &amp;auto_ptr&lt;Data&gt;::operator[](size_t index) const
        {
            return d_data[index];
        }

        template &lt;typename Data&gt;
        inline Data *auto_ptr&lt;Data&gt;::get()
        {
            return d_data;
        }

        template &lt;typename Data&gt;
        inline Data const *auto_ptr&lt;Data&gt;::get() const
        {
            return d_data;
        }

        template &lt;typename Data&gt;
        inline void auto_ptr&lt;Data&gt;::destroy()
        {
            delete[] d_data;
        }

        template &lt;typename Data&gt;
        inline void auto_ptr&lt;Data&gt;::copy(auto_ptr&lt;Data&gt; &amp;other)
        {
            d_data = other.release();
        }

        template &lt;typename Data&gt;
        auto_ptr&lt;Data&gt; &amp;auto_ptr&lt;Data&gt;::operator=(auto_ptr&lt;Data&gt; &amp;rvalue)
        {
            if (this != &amp;rvalue)
            {
                destroy();
                copy(rvalue);
            }
            return *this;
        }

        template &lt;typename Data&gt;
        Data *auto_ptr&lt;Data&gt;::release()
        {
            Data *ret = d_data;
            d_data = 0;
            return ret;
        }

        template &lt;typename Data&gt;
        void auto_ptr&lt;Data&gt;::reset(Data *ptr)
        {
            destroy();
            d_data = ptr;
        }

    } // FBB
</pre>
    The class interface shows the following features:
    <ul>
    <li> If it is assumed that the template type <code>Data</code> is an ordinary type,
the class interface appears to have no special characteristics at all. It
looks like any old class interface. This is generally true. Often a template
class can easily be constructed after having constructed the class for one or
two concrete types, followed by an abstraction phase changing all necessary
references to concrete data types into generic data types, which then become
the template's type parameters.
    <li> At closer inspection, some special characteristics can actually be
discerned. The parameters of the class's copy constructor and overloaded
assignment operators aren't references to plain <code>auto_ptr</code> objects, but
rather references to <code>auto_ptr&lt;Data&gt;</code> objects. Template class objects (or
their references or pointers) <em>always</em> require the template type parameters
to be specified.
    <li> Different from the standard design of copy constructors and
overloaded assignment operators, their parameters are <em>non-</em><code>const</code>
references. This has nothing to do with the class being a template class, but
is a consequence of <code>auto_ptr</code>'s design itself: both the copy constructor
and the overloaded assignment operator take the other's object's pointer,
effectively changing the other object into a <a name="an2653"></a>
0-pointer.
    <li> Like ordinary classes, members can be defined <em>inline</em>. Actually,
<em>all</em> template class members are defined inline (when using precompiled
templates
        <a name="an2654"></a>
<em>precompiled templates</em>
        <a name="an2655"></a>

    this doesn't change; it only means that the compiler has reorganized the
template definition so that it can process the definition faster).
As noted in section <a href="cplusplus06.html#INLINE">6.3</a>, the definition may be put inside the
        <a name="an2656"></a>

class interface or outside (i.e., following) the class interface. As a
        <a name="an2657"></a>
rule of thumb
    the same design principles should be followed here as with concrete
classes: they should be defined below the interface to keep the interface
clean and readable. Long implementations in the interface tend to obscure the
interface itself.
    <li> When objects of a template class are instantiated, the definitions of
all the template's member functions that are used (but <em>only</em> those) must
have been seen by the compiler. Although that characteristic of templates
could be refined to the point where each definition is stored in a separate
template function definition file, including only the definitions of the
template functions that are actually needed, it is hardly ever done that way
(even though it would speed up the required compilation time). Instead, the
usual way to define template classes is to define the interface, defining some
functions inline, and to define the remaining template functions immediately
below the template class's interface.
    <li> Beside the dereference operator (<code>operator*()</code>), the well-known
pair of <a name="an2658"></a>
<code>operator[]()</code> members are defined. Since the class receives no
information about the size of the array of objects, these members cannot
support <a name="an2659"></a>
array-bound checking.
    </ul>
    Let's have a look at some of the member functions defined beyond the class
interface.     Note in particular:
    <ul>
    <li> The definition below the interface is the actual template
definition. Since it is a definition it must start with a 
    <a name="an2660"></a>
<code>template phrase</code>. The function's <em>declaration</em> must also start with a
<a name="an2661"></a>
<code>template</code> phrase, but that is implied by the interface itself, which
already provides the required phrase at its very beginning;
    <li> Wherever <code>auto_ptr</code> is mentioned in the implementation, the
template's type parameter is mentioned as well. This is obligatory.
        </ul>
    Some remarks about specific members:
    <ul>
    <li> The advised <code>copy()</code> and <code>destroy()</code> members (see section
<a href="cplusplus07.html#CopyDestroy">7.5.1</a>) are very simple, but were added to the implementation to
promote standardization of classes containing pointer members.
    <li> The overloaded assignment constructor still has to check for
<a name="an2662"></a>
auto-assignment. 
    </ul>
    Now that the class has been defined, it can be used. To use the class, its
object must be instantiated for a particular data type. The example defines a
new <code>std::string</code> array, storing all command-line arguments. Then, the first
command-line argument is printed. Next, the <code>auto_ptr</code> object is used to
initialize another <code>auto_ptr</code> of the same type. It is shown that the
original <code>auto_ptr</code> now holds a 0-pointer, and that the second <code>auto_ptr</code>
object now holds the command-line arguments:
        <pre>
    #include &lt;iostream&gt;
    #include &lt;algorithm&gt;
    #include &lt;string&gt;
    #include "autoptr.h"
    using namespace std;

    int main(int argc, char **argv)
    {
        FBB::auto_ptr&lt;string&gt; sp(new string[argc]);
        copy(argv, argv + argc, sp.get());

        cout &lt;&lt; "First auto_ptr, program name: " &lt;&lt; sp[0] &lt;&lt; endl;

        FBB::auto_ptr&lt;string&gt; second(sp);

        cout &lt;&lt; "First auto_ptr, pointer now: " &lt;&lt; sp.get() &lt;&lt; endl;
        cout  &lt;&lt; "Second auto_ptr, program name: " &lt;&lt; second[0] &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        First auto_ptr, program name: a.out
        First auto_ptr, pointer now: 0
        Second auto_ptr, program name: a.out
    */
</pre>
<p>
<a name="l338"></a>
<h3>19.1.1: Default template class parameters</h3>
    <a name="templateclasses/default"></a>    Different from template functions, template parameters of template
classes may be given default values.
        <a name="an2663"></a>

    This holds true both for template type- and template non-type
parameters. If a template class is instantiated without specifying arguments
for its template parameters, and if default template parameter values were
defined, then the defaults are used. When defining such defaults keep in mind
that the defaults should be suitable for the majority of instantiations of the
class. E.g., for the template class <code>FBB::auto_ptr</code> the template's type
parameter list could have been altered by specifying <code>int</code> as its default
type:
        <pre>
        template &lt;typename Data = int&gt;
</pre>
    Even though default arguments can be specified, the compiler must still be
informed that object definitions refer to templates. So, when instantiating
template class objects for which default parameter values have been defined
the type specifications may be omitted, but the angle brackets must
remain. So, assuming a default type for the <code>FBB::auto_ptr</code> class, an object
of that class may be defined as:
        <pre>
        FBB::auto_ptr&lt;&gt; intAutoPtr;
</pre>
    No defaults must be specified for template members defined outside of
their class interface. Template functions, even template member functions,
cannot specify default parameter values. So, the definition of, e.g., the
<code>release()</code> member will always begin with the same <code>template</code>
specification:
        <pre>
        template &lt;typename Data&gt;
</pre>
<p>
When a template class uses multiple template parameters, all may be given
default values. However, like default function arguments, once a default value
is used, all remaining parameters must also use their default values. A
template type specification list may not start with a comma, nor may it
contain multiple consecutive commas.
<p>
<a name="l339"></a>
<h3>19.1.2: Declaring template classes</h3>
    <a name="templateclasses/declaring"></a>    Template classes may also be <em>declared</em>. This may be useful in
situations where forward class declarations are required. To declare a
        <a name="an2664"></a>

    template class, replace its interface (the part between the curly braces)
by a semicolon:
        <pre>
    namespace FBB
    {
        template &lt;typename Type&gt;
        class auto_ptr;
    }
</pre>
    Here default types may also be specified. However, default type values
cannot be specified in both the declaration and the definition of a template
class. As a <a name="an2665"></a>
rule of thumb default values should be omitted from
<em>declarations</em>, as template class declarations are never used when
instantiating objects, but only for the occasional forward reference. Note
that this differs from default parameter value specifications for member
functions in concrete classes. Such defaults should be specified in the member
functions' declarations and <em>not</em> in their definitions.
<p>
<a name="DISTINGUISH"></a><a name="l340"></a>
<h3>19.1.3: Distinguishing members and types of formal class-types</h3>
    <a name="templateclasses/distinguish"></a>    Since a template type name may refer to any type, a template's type name
might also refer to a template or a class itself. Let's assume a template
class <code>Handler</code> defines a <code>typename Container</code> as its type parameter, and
a data member storing the container's <code>begin()</code> iterator. Furthermore, the
template class <code>Handler</code> has a constructor accepting any container
supporting a <code>begin()</code> member. The skeleton of our
class <code>Handler</code> could then be:
        <pre>
    template &lt;typename Container&gt;
    class Handler
    {
        Container::const_iterator d_it;

        public:
            Handler(Container const &amp;container)
            :
                d_it(container.begin())
            {}
    };
</pre>
    What were the considerations we had in mind when designing this class?
    <ul>
    <li> The typename <code>Container</code> represents any container supporting
iterators.
    <li> The container presumably supports a member <code>begin()</code>. The
initialization <code>d_it(container.begin())</code> clearly depends on the
template's type parameter, so it's only checked for basic syntactical
correctness.
    <li> Likewise, the container presumably supports a type
<code>const_iterator</code>, defined in the class <code>Container</code>. Since <code>container</code> is
a <code>const</code> reference, the iterator returned by <code>begin()</code> is a
<code>const_iterator</code> rather than a plain <code>iterator</code>.
    </ul>
    Now, when instantiating a <code>Handler</code> using the following <code>main()</code>
function we run into a compilation error:
        <pre>
    #include "handler.h"
    #include &lt;vector&gt;
    using namespace std;

    int main()
    {
        vector&lt;int&gt; vi;
        Handler&lt;vector&lt;int&gt; &gt; ph(vi);
    }
    /*
        Reported error:

    handler.h:4: error: syntax error before `;' token
    */
</pre>
    Apparently the line
        <pre>
        Container::const_iterator d_it;
</pre>
    in the <code>Handler</code> class causes a problem. The problem is the following:
when using template type parameters, a plain syntax check allows the compiler
to decide that `<code>container</code>' refers to a <code>Container</code> object. Such a
<code>Container</code> might very well support a <code>begin()</code> member, hence
<code>container.begin()</code> is syntactically correct. However, for a actual
<code>Container</code> type that member <code>begin()</code> might not have been implemented. Of
course, whether or not <code>begin()</code> has in fact been implemented will only be
known by the time <code>Container</code>'s actual type has been specified.
<p>
On the other hand, note that the compiler is unable to determine what a
<code>Container::const_iterator</code> is. The compiler takes the easy way out, and
assumes <code>const_iterator</code> is a member of the as yet mysterious
<code>Container</code>. Therefore, a plain syntax check clearly fails, as the statement
        <pre>
        Container::const_iterator d_it;
</pre>
    is always syntactically wrong when <code>const_iterator</code> is a member or
enum-value of <code>Container</code>. Of course, <em>we</em> know better, since we have a
type that is nested under the class <code>Container</code> in mind. The compiler,
however, doesn't know that and before it has parsed the complete definition,
it has already read <code>Container::const_iterator</code>. At that point the compiler
has already made up its mind, assuming that <code>Container::const_iterator</code> will
be a member, rather than a type.
<p>
That the compiler indeed assumes <code>X::a</code> is a member <code>a</code> of the class
<code>X</code> is illustrated by the error message we get when we try to compile
<code>main()</code> using the following implementation of <code>Handler</code>'s constructor:
        <pre>
    Handler(Container const &amp;container)
    :
        d_it(container.begin())
    {
        size_t x = Container::ios_end;
    }
    /*
        Reported error:

        error: `ios_end' is not a member of type `std::vector&lt;int,
                std::allocator&lt;int&gt; &gt;'
    */
</pre>
    In cases like these, where the intent is to refer to a <em>type</em> defined in
(or depending on) a template class like <code>Container</code>, this must explicitly be
indicated to the
    <a name="an2666"></a>

compiler, using the <code>typename</code> keyword. Here is the <code>Handler</code> class once
again, now using <code>typename</code>:
        <pre>
    template &lt;typename Container&gt;
    class Handler
    {
        typename Container::const_iterator d_it;
        public:
            Handler(Container const &amp;container);
    };

    template &lt;typename Container&gt;
    inline Handler&lt;Container&gt;::Handler(Container const &amp;container)
    :
        d_it(container.begin())
    {}
</pre>
    Now <code>main()</code> will compile correctly. The <code>typename</code> keyword may also
be required when specifying the proper return types of template class member
functions returning values of nested types defined within the template
class. Section <a href="cplusplus19.html#RETURNNESTED">19.11.2</a> provides an example of this situation.
<p>
<a name="l341"></a>
<h3>19.1.4: Non-type parameters</h3>
    <a name="templateclasses/nontype"></a>    As we've seen with template functions, template parameters are either
template type parameters or template non-type parameters. Template classes may
also define non-type parameters. Like the non-const parameters used with
template functions they must be constants whose values are known by the time
an object is instantiated.
<p>
However, their values are not deduced by the compiler using arguments
passed to constructors. Assume we modify the template class <code>FBB::auto_ptr</code>
so that it has an additional non-type parameter <code>size_t Size</code>. Next we use
this <code>Size</code> parameter in a new constructor defining an array of <code>Size</code>
elements of type <code>Data</code> as its parameter. The new <code>FBB::auto_ptr</code> template
class becomes (showing only the relevant constructors; note the two template
type parameters that are now required, e.g., when specifying the type of the
copy constructor's parameter):
        <pre>
    namespace FBB
    {
        template &lt;typename Data, size_t Size&gt;
        class auto_ptr
        {
            Data *d_data;
            size_t d_n;

            public:
                auto_ptr(auto_ptr&lt;Data, Size&gt; &amp;other);
                auto_ptr(Data2 *data);
                auto_ptr(Data const (&amp;arr)[Size]);
                ...
        };

        template &lt;typename Data, size_t Size&gt;
        inline auto_ptr&lt;Data, Size&gt;::auto_ptr(Data const (&amp;arr)[Size])
        :
            d_data(new Data2[Size]),
            d_n(Size)
        {
            std::copy(arr, arr + Size, d_data);
        }
    }
</pre>
    Unfortunately, this new setup doesn't satisfy our needs, as the values of
template non-type parameters are not deduced by the compiler. When the
compiler is asked to compile the following <code>main()</code> function it reports a
mismatch between the required and actual number of template parameters:
        <pre>
    int main()
    {
        int arr[30];

        FBB::auto_ptr&lt;int&gt; ap(arr);
    }
    /*
        Error reported by the compiler:

        In function `int main()':
            error: wrong number of template arguments (1, should be 2)
            error: provided for `template&lt;class Data, size_t Size&gt;
                   class FBB::auto_ptr'
    */
</pre>
    Making <code>Size</code> into a non-type parameter having a default value doesn't
work either. The compiler will use the default, unless explicitly specified
otherwise. So, reasoning that <code>Size</code> can be 0 unless we need another value,
we might specify <code>size_t Size = 0</code> in the templates parameter type list.
However, this causes a mismatch between the default value 0 and the actual
size of the array <code>arr</code> as defined in the above <code>main()</code> function. The
compiler, using the default value, reports:
        <pre>
    In instantiation of `FBB::auto_ptr&lt;int, 0&gt;':
    ...
    error: creating array with size zero (`0')
</pre>
    So, although template classes may use non-type parameters, they must be
specified like the type parameters when an object of the class is
defined. Default values can be specified for those non-type parameters, but
then the default will be used when the non-type parameter is left unspecified.
<p>
Note that <a name="an2667"></a>

    <a name="an2668"></a>
<em>default template parameter value</em><em>s</em> (either type or non-type
template parameters) may <em>not</em> be used when template member functions are
defined outside the class interface.  Template function definitions (and thus:
template class member functions) may not be given default template (non) type
parameter values. If default template parameter values are to be used for
template class members, they have to be specified in the class interface.
<p>
Similar to  non-type parameters of template functions, non-type parameters
of template classes may only be specified as constants:
    <ul>
    <li> Global <a name="an2669"></a>
 variables have constant addresses, which
can be used as arguments for non-type parameters.
    <li> Local <a name="an2670"></a>
 and <a name="an2671"></a>
dynamically allocated variables have
addresses that are not known by the compiler when the source file is
compiled. These addresses can therefore not be used as arguments for non-type
parameters.
    <li> Lvalue <a name="an2672"></a>
 transformations are allowed: if a
pointer is defined as a non-type parameter, an array name may be specified.
    <li> <a name="an2673"></a>
 Qualification <a name="an2674"></a>

conversions are allowed: a pointer to a non-const object may be used with a
non-type parameter defined as a <code>const</code> pointer.
    <li> Promotions <a name="an2675"></a>
 are allowed: a constant of a `narrower'
data type may be used for the specification of a non-type parameter of a
`wider' type (e.g., a <code>short</code> can be used when an <code>int</code> is called for, a
<code>long</code> when a <code>double</code> is called for).
    <li> Integral <a name="an2676"></a>
 conversions are allowed: if an
<code>size_t</code> parameter is specified, an <code>int</code> may be used too.
    <li> Variables cannot be used to specify template non-type parameters, as
their values are not constant expressions. Variables defined using the
<code>const</code> modifier, however, may be used, as their values never change.
    </ul>
<p>
Although our attempts to define a constructor of the class
<code>FBB::auto_ptr</code> accepting an array as its argument, allowing us to use the
array's size within the constructor's code has failed so far, we're not yet
out of options. In the next section an approach will be described allowing us
to reach our goal, after all.
<p>
<a name="l342"></a>
<h2>19.2: Member templates</h2>
    <a name="templateclasses/membertemplates"></a>    Our previous attempt to define a template non-type parameter which is
initialized by the compiler to the number of elements of an array failed
because the template's parameters are not implicitly deduced when a
constructor is called, but they are explicitly specified, when an object of
the template class is defined. As the parameters are specified just before the
template's constructor is called, there's nothing to deduce anymore, and the
compiler will simply use the explicitly specified template arguments.
<p>
On the other hand, when template <em>functions</em> are used, the actual
template parameters are deduced from the arguments used when calling the
function. This opens an approach route to the solution of our problem. If the
constructor itself is made into a member which itself is a template function
(containing a <a name="an2677"></a>
template announcement of its own), then the compiler
will be able to deduce the non-type parameter's value, without us having to
specify it explicitly as a template class non-type parameter.
<p>
Member functions (or classes) of template classes which themselves are
templates are called <em>member templates</em>.
        <a name="an2678"></a>

        <a name="an2679"></a>

    Member templates are defined in the same way as any other template,
including the <code>template &lt;typename ...&gt;</code> header.
<p>
When converting our earlier <code>FBB::auto_ptr(Data const (&amp;array)[Size])</code>
constructor into a member template we may use the template class's <code>Data</code>
type parameter, but must provide the member template with a non-type parameter
of its own. The class interface is given the following additional member
declaration:
        <pre>
    template &lt;typename Data&gt;
    class auto_ptr
    {
        ...
        public:
            template &lt;size_t Size&gt;
            auto_ptr(Data const (&amp;arr)[Size]);
        ...
    };
</pre>
    and the constructor's implementation becomes:
        <pre>
    template &lt;typename Data&gt;
    template &lt;size_t Size&gt;
    inline auto_ptr&lt;Data&gt;::auto_ptr(Data const (&amp;arr)[Size])
    :
        d_data(new Data[Size]),
        d_n(Size)
    {
        std::copy(arr, arr + Size, d_data);
    }
</pre>
<p>
Member templates have the following characteristics:
    <ul>
    <li> Normal <a name="an2680"></a>
access rules apply: the constructor
can be used
by the general program to construct an <code>FBB::auto_ptr</code> object of a given
data type. As usual for template classes, the data type must be specified when
the object is constructed. To construct an <code>FBB::auto_ptr</code> object from the
array <code>int array[30]</code> we define:
    <pre>
        FBB::auto_ptr&lt;int&gt; object(array);
</pre>
    <li> Any member can be defined as a member template, not just a
constructor.
    <li> When a template member is defined below its class, the template class
    <a name="an2681"></a>
 parameter list must
precede the template function parameter list of the template
member. Furthermore: 
        <ul>
        <li> The member should be defined inside its proper namespace
environment. The organization within files defining template classes within a
namespace should therefore be:
        <pre>
    namespace SomeName
    {
        template &lt;typename Type, ...&gt;   // template class definition
        class ClassName
        {
            ...
        };

        template &lt;typename Type, ...&gt;   // non-inline member definition(s)
        ClassName&lt;Type, ...&gt;::member(...)
        {
            ...
        }
    }                                   // namespace closed
</pre>
        <li> Two template announcements must be used: the template class's
template announcement is specified first, followed by the member template's
template announcement.
        <li> The definition itself must specify the member template's
proper scope: the member template is defined as a member of the class
<code>FBB::auto_ptr</code>, instantiated for the formal template parameter type
<code>Data</code>. Since we're already inside the namespace <code>FBB</code>, the function
header starts with <code>auto_ptr&lt;Data&gt;::auto_ptr</code>.
        <li> The formal template parameter names in the declaration and
implementation must be identical.
        </ul>
    </ul>
    One small problem remains. When we're constructing an <code>FBB::auto_ptr</code>
object from a fixed-size array the above constructor is not used. Instead, the
constructor <code>FBB::auto_ptr&lt;Data&gt;::auto_ptr(Data *data)</code> is activated. As the
latter constructor is not a member template, it is considered a more
specialized version of a constructor of the class <code>FBB::auto_ptr</code> than the
former constructor. Since both constructors accept an array the compiler will
call <code>auto_ptr(Data *)</code> rather than <code>auto_ptr(Data const
(&amp;array)[Size])</code>. This problem can be solved by simply changing the
constructor <code>auto_ptr(Data *data)</code> into a member template as well, in which
case its template type parameter should be changed into `<code>Data</code>'. The only
remaining subtlety is that template parameters of member templates may not
shadow
        <a name="an2682"></a>

        <a name="an2683"></a>

    the template parameters of their class. Renaming <code>Data</code> into <code>Data2</code>
takes care of this subtlety. Here is the (inline) definition of the
<code>auto_ptr(Data *)</code> constructor, followed by an example in which both
constructors are actually used:
        <pre>
    template &lt;typename Data&gt;
    template &lt;typename Data2&gt;           // data: dynamically allocated
    inline auto_ptr&lt;Data&gt;::auto_ptr(Data2 *data)
    :
        d_data(data),
        d_n(0)
    {}
</pre>
    Calling both constructors in <code>main()</code>:
        <pre>
    int main()
    {
        int array[30];

        FBB::auto_ptr&lt;int&gt; ap(array);
        FBB::auto_ptr&lt;int&gt; ap2(new int[30]);

        return 0;
    }
</pre>
<p>
<a name="l343"></a>
<h2>19.3: Static data members</h2>
<a name="templateclasses/static"></a>    When <a name="an2684"></a>
static members are defined in template classes, they
        <a name="an2685"></a>

    are instantiated for every new <a name="an2686"></a>
instantiation. As they are static
members, there will be only one member when multiple objects of the <em>same</em>
template type(s) are defined. For example, in a class like:
        <pre>
    template &lt;typename Type&gt;
    class TheClass
    {
        static int s_objectCounter;
    };
</pre>
    There will be <em>one</em> <code>TheClass&lt;Type&gt;::objectCounter</code> for each different
<code>Type</code> specification. The following instantiates just one single
static variable, shared among the different objects:
        <pre>
    TheClass&lt;int&gt; theClassOne;
    TheClass&lt;int&gt; theClassTwo;
</pre>
    Mentioning static members in interfaces does not mean these members are
actually defined: they are only <em>declared</em> by their classes and must be
<em>defined</em> separately.  With static members of template classes this is not
different. The <a name="an2687"></a>
definitions of static members
        <a name="an2688"></a>

    are usually provided immediately following (i.e., below) the template
class interface. The static member <code>s_objectCounter</code> will thus be defined as
follows, just below its class interface:
        <pre>
    template &lt;typename Type&gt;                    // definition, following
    int TheClass&lt;Type&gt;::s_objectCounter = 0;    // the interface
</pre>
    In the above case, <code>s_objectCounter</code> is an <code>int</code> and thus independent
of the template type parameter <code>Type</code>.
<p>
In a list-like construction, where a <a name="an2689"></a>
pointer to objects of the class
itself is required, the template type parameter <code>Type</code> must be used to
define the static variable, as shown in the following example:
        <pre>
    template &lt;typename Type&gt;
    class TheClass
    {
        static TheClass *s_objectPtr;
    };

    template &lt;typename Type&gt;
    TheClass&lt;Type&gt; *TheClass&lt;Type&gt;::s_objectPtr = 0;
</pre>
    As usual, the definition can be read from the variable name back to the
beginning of the definition: <code>s_objectPtr</code> of the class <code>TheClass&lt;Type&gt;</code>
is a pointer to an object of <code>TheClass&lt;Type&gt;</code>.
<p>
Finally, when a static variable of a template's type parameter is defined,
it should of course not be given the initial value 0. The default constructor
(e.g., <code>Type()</code> will usually be more appropriate):
        <pre>
    template &lt;typename Type&gt;                    // s_type's definition
    Type TheClass&lt;Type&gt;::s_type = Type();
</pre>
<p>
<a name="l344"></a>
<h2>19.4: Specializing template classes for deviating types</h2>
<a name="templateclasses/specialization"></a>    Our earlier class <code>FBB::auto_ptr</code> can be used for many different
types. Their common characteristic is that they can simply be assigned to the
class's <code>d_data</code> member, e.g., using <code>auto_ptr(Data *data)</code>. However,
this is not always as simple as it looks. What if <code>Data</code>'s actual type is
<code>char *</code>? Examples of a <code>char **</code>, <code>data</code>'s resulting type, are
well-known: <code>main()</code>'s <code>argv</code> and <code>envp</code>, for example are <code>char **</code>
parameters.
<p>
It this special case we might not be interested in the mere reassignment
of the constructor's parameter to the class's <code>d_data</code> member, but we might
be interested in copying the complete <code>char **</code> structure. To realize this,
template class specializations may be used.
<p>
Template class specializations are used in cases where template member
        <a name="an2690"></a>

    functions cannot (or should not) be used for a particular actual template
parameter type. In those cases specialized template members can be
constructed, fitting the special needs of the actual type.
<p>
Template class member specializations are specializations of existing
class members. Since the class members already exist, the specializations will
<em>not</em> be part of the class interface. Rather, they are defined below the
interface as members, redefining the more generic members using explicit
types. Furthermore, as they are specializations of existing class members,
their function prototypes must exactly match the prototypes of the member
functions for which they are specializations. For our <code>Data = char *</code>
specialization the following definition could be designed:
        <pre>
    template &lt;&gt;
    auto_ptr&lt;char *&gt;::auto_ptr(char **argv)
    :
        d_n(0)
    {
        char **tmp = argv;
        while (*tmp++)
            d_n++;
        d_data = new char *[d_n];

        for (size_t idx = 0; idx &lt; d_n; idx++)
        {
            std::string str(argv[idx]);
            d_data[idx] =
                strcpy(new char[str.length() + 1], str.c_str());
        }
    }
</pre>
    Now, the above specialization will be used to construct the following
<code>FBB::auto_ptr</code> object:
        <pre>
    int main(int argc, char **argv)
    {
        FBB::auto_ptr&lt;char *&gt; ap3(argv);
        return 0;
    }
</pre>
<p>
Although defining a template member specialization may allow us to use the
occasional exceptional type, it is also quite possible that a single template
member specialization is not enough. Actually, this is the case when designing
the <code>char *</code> specialization, since the template's <code>destroy()</code>
implementation is not correct for the specialized type <code>Data = char *</code>. When
multiple members must be specialized for a particular type, then a complete
template class specialization might be considered.
<p>
A completely specialized class shows the following characteristics:
    <ul>
    <li> The template class specialization follows the generic template class
definition. After all, it's a specialization, so the compiler must have seen
what is being specialized.
    <li> All the class's template parameters are given specific type names or
(for the non-type parameters) specific values. These specific values are
explicitly stated in a template parameter specification list (surrounded by
angle brackets) which is inserted immediately following the template's class
name.
    <li> All the specialized template members specify the specialized types
and values where the generic template parameters are used in the generic
template definition.
    <li> Not all the template's members <em>have</em> to be defined, but, to
ensure generality of the specialization, <em>should</em> be defined. If a member is
left out of the specialization, it can't be used for the specialized type(s).
    <li> Additional members may be defined in the specialization. However,
those that are defined in the generic template too must have corresponding
members (using the same prototypes, albeit using the generic template
parameters) in the generic template class definition. The compiler will not
complain when additional members are defined, and will allow you to use those
members with objects of the specialized template class.
    <li> Member functions of specialized template classes may be defined
within their specializing class or they may be declared in the specializing
class. When they are only declared, then their definitition should be given
below the specialized template class's interface. Such an implementation may
<em>not</em> begin with a <code>template &lt;&gt;</code> announcement, but should immediately
start with the member function's header.
    </ul>
<p>
Below a full specialization of the template class <code>FBB::auto_ptr</code> for
the actual type <code>Data = char *</code> is given, illustrating the above
characteristics. The specialization should be appended to the file already
containing the generic template class. To reduce the size of the example
members that are only declared may be assumed to have identical
implementations as used in the generic template.
        <pre>
    #include &lt;iostream&gt;
    #include &lt;algorithm&gt;
    #include "autoptr.h"

    namespace FBB
    {
        template&lt;&gt;
        class auto_ptr&lt;char *&gt;
        {
            char **d_data;
            size_t d_n;

            public:
                auto_ptr&lt;char *&gt;();
                auto_ptr&lt;char *&gt;(auto_ptr&lt;char *&gt; &amp;other);
                auto_ptr&lt;char *&gt;(char **argv);

                // template &lt;size_t Size&gt;             NI
                // auto_ptr(char *const (&amp;arr)[Size])

                ~auto_ptr();
                auto_ptr&lt;char *&gt; &amp;operator=(auto_ptr&lt;char *&gt; &amp;rvalue);
                char *&amp;operator[](size_t index);
                char *const &amp;operator[](size_t index) const;
                char **get();
                char *const *get() const;
                char **release();
                void reset(char **argv);
                void additional() const;    // just an additional public
                                            // member
            private:
                void full_copy(char **argv);
                void copy(auto_ptr&lt;char *&gt; &amp;other);
                void destroy();
        };

        inline auto_ptr&lt;char *&gt;::auto_ptr()
        :
            d_data(0),
            d_n(0)
        {}

        inline auto_ptr&lt;char *&gt;::auto_ptr(auto_ptr&lt;char *&gt; &amp;other)
        {
            copy(other);
        }

        inline auto_ptr&lt;char *&gt;::auto_ptr(char **argv)
        {
            full_copy(argv);
        }

        inline auto_ptr&lt;char *&gt;::~auto_ptr()
        {
            destroy();
        }

        inline void auto_ptr&lt;char *&gt;::reset(char **argv)
        {
            destroy();
            full_copy(argv);
        }

        inline void auto_ptr&lt;char *&gt;::additional() const
        {}

        inline void auto_ptr&lt;char *&gt;::full_copy(char **argv)
        {
            d_n = 0;
            char **tmp = argv;
            while (*tmp++)
                d_n++;
            d_data = new char *[d_n];

            for (size_t idx = 0; idx &lt; d_n; idx++)
            {
                std::string str(argv[idx]);
                d_data[idx] =
                    strcpy(new char[str.length() + 1], str.c_str());
            }
        }

        inline void auto_ptr&lt;char *&gt;::destroy()
        {
            while (d_n--)
                delete d_data[d_n];
            delete[] d_data;
        }
    }
</pre>
<p>
<a name="PARTIAL"></a><a name="l345"></a>
<h2>19.5: Partial specializations</h2>     
<a name="templateclasses/partial"></a>    In the previous section we've seen that it is possible to design template
class specializations. It was shown that both template class members and
complete template classes could be specialized. Furthermore, the
specializations we've seen were specializing template type parameters.
<p>
In this section we'll introduce a variant of these specializations, both
in number and types of template parameters that are specialized.
<em>Partial specializations</em> may be defined for template classes having
        <a name="an2691"></a>

        <a name="an2692"></a>

    multiple template parameters. With partial specializations a subset (any
subset) of template type parameters are given specific values.
<p>
Having discussed specializations of template type parameters in
the previous section, we'll discuss specializations of non-type parameters in
the current section. Partial specializations of template non-type parameters
will be illustrated using some simple concepts defined in matrix algebra, a
branch of linear algebra.
<p>
A matrix is commonly thought of as consisting of a table of a certain
number of rows and columns, filled with numbers. Immediately we recognize an
opening for using templates: the numbers might be plain <code>double</code> values, but
they could also very well be complex numbers, for which our
    <a name="an2693"></a>
<em>complex container</em> (cf. section <a href="cplusplus12.html#COMPLEX">12.4</a>) might prove
useful. Consequently, our template class should be given a <code>DataType</code>
template type parameter, for which a concrete class can be specified when a
matrix is constructed. Some simple matrices, using <code>double</code> values, are:
        <pre>
    1   0   0           An identity matrix,
    0   1   0           a 3 x 3 matrix.
    0   0   1

    1.2  0    0    0    A rectangular matrix,
    0.5  3.5  18  23    a 2 x 4 matrix.

    1   2   4   8       A matrix of one row,
                        a 1 x 4 matrix, also known as a
                        `row vector' of 4 elements.
                        (column vectors are analogously defined)
</pre>
    Since matrices consist of a specific number of rows and columns (the
<em>dimensions</em> of the matrix), which normally do not change when using
matrices, we might consider specifying their values as template non-type
parameters. Since the <code>DataType = double</code> selection will be used in the
majority of cases, <code>double</code> can be selected as the template's default
type. Since it's having a sensible default, the <code>DataType</code> template type
parameter is put last in the template type parameter list. So, our template
class <code>Matrix</code> starts off as follows:
        <pre>
    template &lt;size_t Rows, size_t Columns, typename DataType = double&gt;
    class Matrix
    ...
</pre>
<p>
Various operations are defined on matrices. They may, for example be
added, subtracted or multiplied. We will not focus on these operations
here. Rather, we'll concentrate on a simple operation: computing marginals and
sums. The row marginals are obtained by computing, for each row, the sum of
all its elements, putting these <code>Rows</code> sum values in corresponding elements
of a column vector of <code>Rows</code> elements. Analogously, column marginals are
obtained by computing, for each column, the sum of all its elements, putting
these <code>Columns</code> sum values in corresponding elements of a row vector of
<code>Columns</code> elements. Finally, the sum of the elements of a matrix can be
computed. This sum is of course equal to the sum of the elements of its
marginals. The following example shows a matrix, its marginals, and its sum:
        <pre>
                matrix:         row
                                marginals:

                1   2   3        6
                4   5   6       15

    column      5   7   9       21  (sum)
    marginals
</pre>
    So, what do we want our template class to offer?
    <ul>
    <li> It needs a place to store its matrix elements. This can be defined as
an array of `<code>Rows</code>' rows each containing `<code>Columns</code>' elements of type
<code>DataType</code>. It can be an array, rather than a pointer, since the matrix'
dimensions are known <em>a priori</em>. Since a vector of <code>Columns</code> elements (a
<em>row</em> of the matrix), as well as a vector of <code>Row</code> elements (a <em>column</em>
of the matrix) is often used, <em>typedefs</em> could be used by the class. The
class interface's initial section therefore contains:
                <pre>
        typedef Matrix&lt;1, Columns, DataType&gt;    MatrixRow;
        typedef Matrix&lt;Rows, 1, DataType&gt;       MatrixColumn;

        MatrixRow d_matrix[Rows];
</pre>
<p>
<li> It should offer constructors: a default constructor and, for example,
a constructor initializing the matrix from a stream. No copy constructor is
required, since the default copy constructor performs its task
properly. Analogously, no overloaded assignment operator or destructor is
required. Here are the constructors, defined in the public section:
                <pre>
    template &lt;size_t Rows, size_t Columns, typename DataType&gt;
    Matrix&lt;Rows, Columns, DataType&gt;::Matrix()
    {
        std::fill(d_matrix, d_matrix + Rows, MatrixRow());
    }

    template &lt;size_t Rows, size_t Columns, typename DataType&gt;
    Matrix&lt;Rows, Columns, DataType&gt;::Matrix(std::istream &amp;str)
    {
        for (size_t row = 0; row &lt; Rows; row++)
            for (size_t col = 0; col &lt; Columns; col++)
                str &gt;&gt; d_matrix[row][col];
    }
</pre>
<p>
<li> The class's <code>operator[]()</code> member (and its <code>const</code> variant) only
handles the first index, returning a reference to a complete
<code>MatrixRow</code>. How to handle the retrieval of elements in a <code>MatrixRow</code> will
be covered shortly. To keep the example simple, no array bound check has been
implemented:
                <pre>
    template &lt;size_t Rows, size_t Columns, typename DataType&gt;
    Matrix&lt;1, Columns, DataType&gt;
    &amp;Matrix&lt;Rows, Columns, DataType&gt;::operator[](size_t idx)
    {
        return d_matrix[idx];
    }
</pre>
<p>
<li> Now we get to the interesting parts: computing marginals and the sum
of all elements in a <code>Matrix</code>. Considering that marginals are vectors,
either a <code>MatrixRow</code>, containing the column marginals, a <code>MatrixColumn</code>,
containing the row marginals, or a single value, either computed as
the sum of a vector of marginals, or as the value of a <code>1 x 1</code> matrix,
initialized from a generic <code>Matrix</code>, we can now construct <em>partial
specializations</em> to handle <code>MatrixRow</code> and <code>MatrixColumn</code> objects,
and a partial specialization handling <code>1 x 1</code> matrices. Since we're about
to define these specializations, we can use them when computing
marginals and the matrix' sum of all elements. Here are the implementations of
these members:
                <pre>
    template &lt;size_t Rows, size_t Columns, typename DataType&gt;
    Matrix&lt;1, Columns, DataType&gt;
    Matrix&lt;Rows, Columns, DataType&gt;::columnMarginals() const
    {
        return MatrixRow(*this);
    }

    template &lt;size_t Rows, size_t Columns, typename DataType&gt;
    Matrix&lt;Rows, 1, DataType&gt;
    Matrix&lt;Rows, Columns, DataType&gt;::rowMarginals() const
    {
        return MatrixColumn(*this);
    }

    template &lt;size_t Rows, size_t Columns, typename DataType&gt;
    DataType Matrix&lt;Rows, Columns, DataType&gt;::sum()  const
    {
        return rowMarginals().sum();
    }
</pre>
<p>
</ul>
<p>
Template class <em>partial specializations</em> may be defined for any (subset)
        <a name="an2694"></a>

        <a name="an2695"></a>

    of template parameters. They can be defined for template type parameters
and for template non-type parameters alike. Our first partial specialization
defines the special case where we construct a row of a generic <code>Matrix</code>,
specifically aiming at (but not restricted to) the construction of column
marginals. Here is how such a partial specialization is constructed:
    <ul>
    <li> The partial specialization starts by defining all template type
parameters which are <em>not</em> specialized in the partial specialization. This
partial specialization template announcement cannot specify any defaults (like
<code>DataType = double</code>), since the defaults have already been specified by the
generic template class definition. Furthermore, the specialization <em>must</em>
follow the definition of the generic template class definition, or the
compiler will complain that it doesn't know what class is being
specialized. Following the template announcement, the class interface
starts. Since it's a template class (partial) specialization, the class name
is followed by a template type parameter list specifying concrete values or
types for all template parameters specified in this specialization, and using
the template's generic (non-)type names for the remaining template
parameters. In the <code>MatrixRow</code> specialization <code>Rows</code> is specified as 1,
since we're talking here about one single row. Both <code>Columns</code> and
<code>DataType</code> remain to be specified. So, the <code>MatrixRow</code> partial
specialization starts as follows:
                <pre>
    template &lt;size_t Columns, typename DataType&gt;  // no default specified
    class Matrix&lt;1, Columns, DataType&gt;
</pre>
<p>
<li> A <code>MatrixRow</code> contains the data of a single row. So it needs a
data member storing <code>Columns</code> values of type <code>DataType</code>. Since <code>Columns</code>
is a constant value, the <code>d_row</code> data member can be defined as an array:
                <pre>
        DataType d_column[Columns];
</pre>
<p>
<li> The constructors require some attention. The default constructor is
simple. It merely initializes the <code>MatrixRow</code>'s data elements, using
<code>DataType</code>'s default constructor:
                <pre>
    template &lt;size_t Columns, typename DataType&gt;
    Matrix&lt;1, Columns, DataType&gt;::Matrix()
    {
        std::fill(d_column, d_column + Columns, DataType());
    }
</pre>
<p>
However, we also need a constructor initializing a <code>MatrixRow</code> object
with the column marginals of a generic <code>Matrix</code> object. This requires us to
provide the constructor with a non-specialized <code>Matrix</code> parameter. In cases
like this, the <a name="an2696"></a>
rule of thumb is to define a member template allowing us to
keep the general nature of the parameter. Since the generic <code>Matrix</code>
template requires three template parameters, two of which are already provided
by the template specialization, the third parameter must be specified in the
member template's template announcement. Since this parameter refers to the
generic matrix' number of rows, let's simply call it <code>Rows</code>. Here then, is
the definition of the second constructor, initializing the <code>MatrixRow</code>'s
data with the column marginals of a generic <code>Matrix</code> object:
                <pre>
    template &lt;size_t Columns, typename DataType&gt;
    template &lt;size_t Rows&gt;
    Matrix&lt;1, Columns, DataType&gt;::Matrix(
                            Matrix&lt;Rows, Columns, DataType&gt; const &amp;matrix)
    {
        std::fill(d_column, d_column + Columns, DataType());

        for (size_t col = 0; col &lt; Columns; col++)
            for (size_t row = 0; row &lt; Rows; row++)
                d_column[col] += matrix[row][col];
    }
</pre>
<p>
Note the way the constructor's parameter is defined: it's a reference to a
<code>Matrix</code> template, using the additional <code>Row</code> template parameter as well
as the template parameters of the partial specialization itself.
    <li> We don't really require additional members to satisfy our current
needs. To access the data elements of the <code>MatrixRow</code> an overloaded
<code>operator[]()</code> is of course useful. Again, the <code>const</code> variant can be
implemented like the non-<code>const</code> variant. Here is its implementation:
                <pre>
    template &lt;size_t Columns, typename DataType&gt;
    DataType &amp;Matrix&lt;1, Columns, DataType&gt;::operator[](size_t idx)
    {
        return d_column[idx];
    }
</pre>
<p>
</ul>
    Now that we have defined the generic <code>Matrix</code> class as well as the
partial specialization defining a single row, the compiler will select the
row's specialization whenever a <code>Matrix</code> is defined using <code>Row = 1</code>. For
example:
        <pre>
    Matrix&lt;4, 6&gt; matrix;        // generic Matrix template is used
    Matrix&lt;1, 6&gt; row;           // partial specialization is used
</pre>
<p>
The partial specialization for a <code>MatrixColumn</code> is constructed
similarly. Let's present its highlights (the full <code>Matrix</code> template class
definition as well as all its specializations are provided in the
<code>cplusplus.yo.zip</code> archive (at <a href="ftp:://ftp.rug.nl/contrib/frank/documents/annotations/">fpt.rug.nl</a>) in the
file <code>yo/templateclasses/examples/matrix.h</code>):
    <ul>
    <li> The template class partial specialization again starts with a
template announcement. The class definition itself now specifies a fixed
value for the second (generic) template parameter, illustrating that we can
construct partial specializations for every single template parameter; not
just the first or the last:
                <pre>
    template &lt;size_t Rows, typename DataType&gt;
    class Matrix&lt;Rows, 1, DataType&gt;
</pre>
<p>
<li> Its constructors are implemented completely analogously to the way
the <code>MatrixRow</code> constructors were implemented. Their implementations are
left as an exercise to the reader (and they can be found in <code>matrix.h</code>).
    <li> An additional member <code>sum()</code> is defined to compute the sum of the
elements of a <code>MatrixColumn</code> vector. It's implementation is simply realized
using the <code>accumulate()</code> generic algorithm:
                <pre>
    template &lt;size_t Rows, typename DataType&gt;
    DataType Matrix&lt;Rows, 1, DataType&gt;::sum()
    {
        return std::accumulate(d_row, d_row + Rows, DataType());
    }
</pre>
<p>
</ul>
<p>
The reader might wonder what happens if we specify the following matrix:
        <pre>
        Matrix&lt;1, 1&gt; cell;
</pre>
    Is this a <code>MatrixRow</code> or a <code>MatrixColumn</code> specialization? The answer
is: neither. It's <a name="an2697"></a>
ambiguous, precisely because <em>both</em> the columns <em>and</em>
the rows could be used with a (different) template partial specialization. If
such a <code>Matrix</code> is actually required, yet another specialized template must
be designed. Since this template specialization can be useful to
obtain the sum of the elements of a <code>Matrix</code>, it's covered here as well:
    <ul>
    <li> This template class partial specialization also needs a template
announcement, this time only specifying <code>DataType</code>. The class definition
specifies two fixed values, using 1 for both the number of rows and the number
of columns:
                <pre>
    template &lt;typename DataType&gt;
    class Matrix&lt;1, 1, DataType&gt;
</pre>
<p>
<li> The specialization defines the usual batch of constructors. Again,
constructors expecting a more generic <code>Matrix</code> type are implemented as
member templates. For example:
                <pre>
    template &lt;typename DataType&gt;
    template &lt;size_t Rows, size_t Columns&gt;
    Matrix&lt;1, 1, DataType&gt;::Matrix(
                            Matrix&lt;Rows, Columns, DataType&gt; const &amp;matrix)
    :
        d_cell(matrix.rowMarginals().sum())
    {}

    template &lt;typename DataType&gt;
    template &lt;size_t Rows&gt;
    Matrix&lt;1, 1, DataType&gt;::Matrix(Matrix&lt;Rows, 1, DataType&gt; const &amp;matrix)
    :
        d_cell(matrix.sum())
    {}
</pre>
<p>
<li> Since <code>Matrix&lt;1, 1&gt;</code> is basically a wrapper around a <code>DataType</code>
value, we need members to access that latter value. A type conversion
operator might be usefull, but we'll also need a <code>get()</code> member to obtain
the value if the conversion operator isn't used by the compiler (which
happens when the compiler is given a choice, see section
<a href="cplusplus09.html#ConversionOperators">9.3</a>). Here are the accessors (leaving out their <code>const</code>
variants):
                <pre>
    template &lt;typename DataType&gt;
    Matrix&lt;1, 1, DataType&gt;::operator DataType &amp;()
    {
        return d_cell;
    }

    template &lt;typename DataType&gt;
    DataType &amp;Matrix&lt;1, 1, DataType&gt;::get()
    {
        return d_cell;
    }
</pre>
<p>
</ul>
    The following <code>main()</code> function shows how the <code>Matrix</code> template class
and its partial specializations can be used:
    <pre>
    #include &lt;iostream&gt;
    #include "matrix.h"
    using namespace std;

    int main(int argc, char **argv)
    {
        Matrix&lt;3, 2&gt; matrix(cin);

        Matrix&lt;1, 2&gt; colMargins(matrix);
        cout &lt;&lt; "Column marginals:\n";
        cout &lt;&lt; colMargins[0] &lt;&lt; " " &lt;&lt; colMargins[1] &lt;&lt; endl;

        Matrix&lt;3, 1&gt; rowMargins(matrix);
        cout &lt;&lt; "Row marginals:\n";
        for (size_t idx = 0; idx &lt; 3; idx++)
            cout &lt;&lt; rowMargins[idx] &lt;&lt; endl;

        cout &lt;&lt; "Sum total: " &lt;&lt; Matrix&lt;1, 1&gt;(matrix) &lt;&lt; endl;
        return 0;
    }
    /*
        Generated output from input: 1 2 3 4 5 6

        Column marginals:
        9 12
        Row marginals:
        3
        7
        11
        Sum total: 21
    */
</pre>
<p>
<a name="l346"></a>
<h2>19.6: Instantiating template classes</h2>
<a name="templateclasses/instantiations"></a>Template <a name="an2698"></a>
 classes are instantiated when an
object of a template class is defined. When a template class object is
defined or declared, the template parameters must explicitly be specified.
<p>
Template parameters are <em>also</em> specified when a template class defines
default template parameter values, albeit that in that case the compiler will
provide the defaults (cf. section <a href="cplusplus19.html#PARTIAL">19.5</a> where <code>double</code> is used as the
default type to be used with the template's <code>DataType</code> parameter).  The
actual values or types of template parameters are
    <a name="an2699"></a>
 <em>never</em> deduced, as with
template functions: to define a <code>Matrix</code> of elements that are complex
values, the following construction is used:
        <pre>
        Matrix&lt;3, 5, std::complex&gt; complexMatrix;
</pre>
    while the following construction defines a matrix of elements that are
<code>double</code> values, with the compiler providing the (default) type <code>double</code>:
        <pre>
        Matrix&lt;3, 5&gt; doubleMatrix;
</pre>
<p>
A template class object may be <em>declared</em> using the keyword <a name="an2700"></a>
<code>extern</code>.
        <a name="an2701"></a>

    For example, the following construction is used to <em>declare</em> the matrix
<code>complexMatrix</code>:
        <pre>
        extern Matrix&lt;3, 5, std::complex&gt; complexMatrix;
</pre>
<p>
<a name="an2702"></a>

        <a name="an2703"></a>

        <a name="an2704"></a>

        <a name="an2705"></a>

        <a name="an2706"></a>

    A template class declaration is sufficient if the compiler encounters
function declarations of functions having return values or parameters which
are template class objects, pointers or references. The following little
source file may be compiled, although the compiler hasn't seen the definition
of the <code>Matrix</code> template class.  Note that generic classes as well as
(partial) specializations may be declared. Furthermore, note that a function
expecting or returning a template class object, reference, or parameter itself
automatically becomes a template function. This is necessary to allow the
compiler to tailor the function to the types of various actual arguments that
may be passed to the function:
        <pre>
    #include &lt;stddef.h&gt;

    template &lt;size_t Rows, size_t Columns, typename DataType = double&gt;
    class Matrix;

    template &lt;size_t Columns, typename DataType&gt;
    class Matrix&lt;1, Columns, DataType&gt;;

    Matrix&lt;1, 12&gt; *function(Matrix&lt;2, 18, size_t&gt; &amp;mat);
</pre>
<p>
When template classes are used they have to be processed by the compiler
first. So, template member functions must be known to the compiler when the
template is instantiated.  This does not mean that all members of a template
class are instantiated when a template class object is defined.
        <a name="an2707"></a>

    The compiler will only instantiate those members that are actually
used. This is illustrated by the following simple class <code>Demo</code>, having two
constructors and two members. When we create a <code>main()</code> function in which
one constructor is used and one member is called, we can make a note of the
sizes of the resulting object file and executable program. Next the class
definition is modified such that the unused constructor and member are
commented out. Again we compile and link the <code>main()</code> function and the
resulting sizes are identical to the sizes obtained earlier (on my computer,
using <code>g++</code> version 4.1.2) these sizes are 3904 bytes (after
stripping). There are other ways to illustrate the point that only members
that are used are instantiated, like using the <a name="an2708"></a>
<code>nm</code> program, showing the
symbolic contents of object files. Using programs like <code>nm</code> will yield the
same conclusion: <em>only template member functions that are actually used are
initialized</em>. Here is an example of the template class <code>Demo</code> used for this
little experiment. In <code>main()</code> only the first constructor and the first
member function are called and thus only these members were instantiated:
        <pre>
    #include &lt;iostream&gt;

    template &lt;typename Type&gt;
    class Demo
    {
        Type d_data;

        public:
            Demo();
            Demo(Type const &amp;value);

            void member1();
            void member2(Type const &amp;value);
    };

    template &lt;typename Type&gt;
    Demo&lt;Type&gt;::Demo()
    :
        d_data(Type())
    {}

    template &lt;typename Type&gt;
    void Demo&lt;Type&gt;::member1()
    {
        d_data += d_data;
    }

    // the following members are commented out before compiling
    // the second program

    template &lt;typename Type&gt;
    Demo&lt;Type&gt;::Demo(Type const &amp;value)
    :
        d_data(value)
    {}

    template &lt;typename Type&gt;
    void Demo&lt;Type&gt;::member2(Type const &amp;value)
    {
        d_data += value;
    }

    int main()
    {
        Demo&lt;int&gt; demo;
        demo.member1();
    }
</pre>
<p>
<a name="l347"></a>
<h2>19.7: Processing template classes and instantiations</h2>
<a name="templateclasses/nameresolution"></a>In section <a href="cplusplus18.html#NAMERESFUN">18.9</a> the distinction between code depending on template
parameters and code not depending on template parameters was introduced.
The same distinction also holds true when template classes are defined and
used.
<p>
Code that does not depend on template parameters is verified by the
compiler when the template is defined. E.g., if a member function in a
template class uses a <a name="an2709"></a>
<code>qsort()</code> function, then <code>qsort()</code> does not depend
on a template parameter. Consequently, <code>qsort()</code> must be known to the
compiler when it encounters the <code>qsort()</code> function call. In practice this
implies that <a name="an2710"></a>
<code>cstdlib</code> or <a name="an2711"></a>
<code>stdlib.h</code> must have been processed by the
compiler before it will be able to process the template class definition.
<p>
On the other hand, if a template defines a <code>&lt;typename Type&gt;</code> template
type parameter, which is the return type of some template member function,
e.g.,
        <pre>
        Type member() ...
</pre>
    then we distinguish the following situations where the compiler encounters
<code>member()</code> or the class to which <code>member()</code> belongs:
    <ul>
    <li> At the location in the source where template class objects are
defined (called the
        <a name="an2712"></a>
<em>point of instantiation</em> of the template class object),
    the compiler will have read the template class definition, performing a
basic check for syntactical correctness of member functions like
<code>member()</code>. So, it won't accept a definition or declaration like <code>Type
&amp;&amp;member()</code>, because <strong>C++</strong> does not support functions returning references
to references. Furthermore, it will check the existence of the actual typename
that is used for instantiating the object. This typename must be known to the
compiler at the object's point of instantiation.
    <li> At the location in the source where <a name="an2713"></a>
template member functions are
used (which is called the template member function's point of instantiation),
the <code>Type</code> parameter must of course still be known, and <code>member()</code>'s
statements that depend on the <code>Type</code> template parameter are now checked for
syntactical correctness. For example, if <code>member()</code> contains a statement
like
        <pre>
        Type tmp(Type(), 15);
</pre>
    then this is in principle a syntactically valid statement. However, when
<code>Type = int</code> and <code>member()</code> is called, its instantiation will fail,
because <code>int</code> does not have a constructor expecting two <code>int</code>
arguments. Note that this is <em>not</em> a problem when the compiler instantiates
an object of the class containing <code>member()</code>: at the point of instantiation
of the object its <code>member()</code> member function is not instantiated, and so the
invalid <code>int</code> construction remains undetected.
    </ul>
<p>
<a name="TEMPFRIENDS"></a><a name="l348"></a>
<h2>19.8: Declaring friends</h2>
<a name="templateclasses/friends"></a>    Friend functions are normally constructed as <em>support</em> functions of a
class that cannot be constructed as class members themselves. The well-known
insertion operator for output streams is a case in point. Friend classes are
most often seen in the context of nested classes, where the inner class
declares the outer class as its friend (or the other way around). Here again
we see a support mechanism: the inner class is constructed to support the
outer class.
<p>
Like concrete classes, template classes may declare other functions and
classes as their friends. Conversely, concrete classes may declare template
classes as their friends. Here too, the friend is constructed as a special
function or class augmenting or supporting the functionality of the declaring
class. Although the <code>friend</code> keyword can thus be used in any type of class
        <a name="an2714"></a>

        <a name="an2715"></a>

    (concrete or template) to declare any type of function or class as a
friend, when using template classes the following cases should be
distinguished:
    <ul>
    <li> A template class may declare a nontemplate function or class to be
its friend. This is a common friend declaration, such as the
        <a name="an2716"></a>
insertion operator for <a name="an2717"></a>
<code>ostream</code> objects.
    <li> A template class may declare another template function or class to be
its friend. In this case, the friend's template parameters may have to be
specified. If the actual values of the friend's template parameters must be
equal to the template parameters of the class declaring the friend, the friend
is said to be a <a name="an2718"></a>
<em>bound friend template</em> class or function. In this case the
template parameters of the template in which a <code>friend</code> declaration is used
determine (<em>bind</em>) the template parameters of the friend class or function,
resulting in a one-to-one correspondence between the template's parameters and
the friend's template parameters.
    <li> In the most general case, a template class may declare another
template function or class to be its friend, irrespective of the friend's
actual template parameters. In this case an <a name="an2719"></a>
<em>unbound friend template</em> class
or function is declared: the template parameters of the friend template class
or function remain to be specified, and are not related in some predefined way
to the template parameters of the class declaring the friend. For example, if
a class has data members of various types, specified by its template
parameters, and another class should be allowed direct access to these data
members (so it should be a friend), we would like to specify any of the
current template parameters to instantiate such a friend. Rather than
specifying multiple bound friends, a single generic (unbound) friend may be
declared, specifying the friend's actual template parameters only when this is
required.
    <li> The above cases, in which a template is declared as a friend, may
also be encountered when concrete classes are used:
        <ul>
        <li> The concrete class declaring concrete friends has already been
covered (chapter <a href="cplusplus11.html#Friends">11</a>).
        <li> The equivalent of bound friends occurs if a concrete class
specifies specific actual template parameters when declaring its friend.
        <li> The equivalent of unbound friends occurs if a concrete class
declares a generic template as its friend.
        </ul>
    </ul>
<p>
<a name="l349"></a>
<h3>19.8.1: Non-template functions or classes as friends</h3>
    <a name="templateclasses/normalfriends"></a>    A template class may declare a concrete function, concrete member function
or complete concrete class as its friend.  Such a <a name="an2720"></a>
friend may access the
template class's <a name="an2721"></a>
private members.
<p>
Concrete classes and ordinary functions can be declared as friends, but
before a single class member function can be declared as a friend, the
compiler must have seen the <a name="an2722"></a>
class interface declaring that member. Let's
consider the various possibilities:
    <ul>
    <li> A template class may declare a concrete function to be its
friend. It is not completely clear <em>why</em> we would like to declare a concrete
function as a friend. In ordinary cases we would like to pass an object of the
class declaring the friend to the function. However, this requires us to
provide the function with a template parameter without specifying its
types. As the language does not support constructions like
        <pre>
        void function(std::vector&lt;Type&gt; &amp;vector)
</pre>
    unless <code>function()</code> itself is a template, it is not immediately clear
how and why such a friend should be constructed. One reason, though, is to
allow the function to access the class's private static members. Furthermore,
such friends could themselves instantiate objects of classes declaring them as
friends, and directly access such object's private members. For example:
                <pre>
    template &lt;typename Type&gt;
    class Storage
    {
        friend void basic();
        static size_t s_time;
        std::vector&lt;Type&gt; d_data;
        public:
            Storage();
    };

    template &lt;typename Type&gt;
    size_t Storage&lt;Type&gt;::s_time = 0;

    template &lt;typename Type&gt;
    Storage&lt;Type&gt;::Storage()
    {}

    void basic()
    {
        Storage&lt;int&gt;::s_time = time(0);
        Storage&lt;double&gt; storage;
        std::random_shuffle(storage.d_data.begin(), storage.d_data.end());
    }
</pre>
<p>
<li> Declaring a concrete class to be a template class's friend probably
has more practical implications. Here the friend-class may instantiate any
kind of object of the template class, to access all of its private members
thereafter. A simple forward declaration of the friend class in front of the
template class definition is enough to make this work:
                <pre>
    class Friend;

    template &lt;typename Type&gt;
    class Composer
    {
        friend class Friend;
        std::vector&lt;Type&gt; d_data;
        public:
            Composer();
    };

    class Friend
    {
        Composer&lt;int&gt; d_ints;
        public:
            Friend(std::istream &amp;input);
    };

    inline::Friend::Friend(std::istream &amp;input)
    {
        std::copy(std::istream_iterator&lt;int&gt;(input),
                  std::istream_iterator&lt;int&gt;(),
                  back_inserter(d_ints.d_data));
    }
</pre>
<p>
<li> Alternatively, just a single member function of a concrete class may
be declared as a friend. This requires that the compiler has read the friend
class's interface before the friend is declared. Omitting the required
destructor and overloaded assignment operators, the following shows an example
of a class whose member <code>randomizer()</code> is declared as a friend of the class
<code>Composer</code>:
                <pre>
    template &lt;typename Type&gt;
    class Composer;

    class Friend
    {
        Composer&lt;int&gt; *d_ints;
        public:
            Friend(std::istream &amp;input);
            void randomizer();
    };

    template &lt;typename Type&gt;
    class Composer
    {
        friend void Friend::randomizer();
        std::vector&lt;Type&gt; d_data;
        public:
            Composer(std::istream &amp;input)
            {
                std::copy(std::istream_iterator&lt;int&gt;(input),
                          std::istream_iterator&lt;int&gt;(),
                          back_inserter(d_data));
            }
    };

    inline Friend::Friend(std::istream &amp;input)
    :
        d_ints(new Composer&lt;int&gt;(input))
    {}

    inline void Friend::randomizer()
    {
        std::random_shuffle(d_ints-&gt;d_data.begin(), d_ints-&gt;d_data.end());
    }
</pre>
<p>
In this example note that <code>Friend::d_ints</code> is a pointer member. It
cannot be a <code>Composer&lt;int&gt;</code> object, since the <code>Composer</code> class interface
hasn't yet been seen by the compiler when it reads <code>Friend</code>'s class
interface. Disregarding this and defining a data member <code>Composer&lt;int&gt;
d_ints</code> results in the compiler generating the error
        <a name="an2723"></a>

        <pre>
        error: field `d_ints' has incomplete type
</pre>
    Incomplete type, as the compiler at this points knows of the existence of
the class <code>Composer</code> but as it hasn't seen <code>Composer</code>'s interface it
doesn't know what size the <code>d_ints</code> data member will have.
    </ul>
<p>
<a name="l350"></a>
<h3>19.8.2: Templates instantiated for specific types as friends</h3>
    <a name="templateclasses/boundfriends"></a>    With <a name="an2724"></a>
<em>bound friend</em> template classes or functions there is a one-to-one
mapping between the actual values of the template-friends' template parameters
and the template class's template parameters declaring them as friends. In this
case, the friends themselves are templates too. Here are the various
possibilities:
    <ul>
    <li> A template function may be declared as a friend of a template
class. In this case we don't experience the problems we encountered with
concrete functions declared as friends of template classes. Since the friend
template function itself is a template, it may be provided with the
required template parameters allowing it to specify a template class
parameter. Thus we can pass an object of the class declaring the template
function as its friend to the template function. The organization of the
various declarations thus becomes:
        <ul>
        <li> The template class declaring the friend is itself declared;
        <li> The template function (to be declared as a friend) is declared;
        <li> The template class declaring the bound template friend function
is defined;
        <li> The (friend) template function is defined, now having access to
all the template class's (private) members.
        </ul>
    Note that the template friend declaration specifies its template
parameters immediately following the template's function name. Without the
template parameter list affixed to the function name, it would be an ordinary
friend function. Here is an example showing the use of a bound friend
to create a subset of the entries of a dictionary. For real life examples,
a dedicated function object returning <code>!key1.find(key2)</code> is probably more
useful, but for the current example, <code>operator==()</code> is acceptable:
                <pre>
    template &lt;typename Key, typename Value&gt;
    class Dictionary;

    template &lt;typename Key, typename Value&gt;
    Dictionary&lt;Key, Value&gt;
               subset(Key const &amp;key, Dictionary&lt;Key, Value&gt; const &amp;dict);

    template &lt;typename Key, typename Value&gt;
    class Dictionary
    {
        friend Dictionary&lt;Key, Value&gt; subset&lt;Key, Value&gt;
                   (Key const &amp;key, Dictionary&lt;Key, Value&gt; const &amp;dict);
        std::map&lt;Key, Value&gt; d_dict;
        public:
            Dictionary();
    };

    template &lt;typename Key, typename Value&gt;
    Dictionary&lt;Key, Value&gt;
               subset(Key const &amp;key, Dictionary&lt;Key, Value&gt; const &amp;dict)
    {
        Dictionary&lt;Key, Value&gt; ret;

        std::remove_copy_if(dict.d_dict.begin(), dict.d_dict.end(),
                            std::inserter(ret.d_dict, ret.d_dict.begin()),
                            std::bind2nd(std::equal_to&lt;Key&gt;(), key));
        return ret;
    }
</pre>
<p>
<li> By declaring a full template class as a template class's friend, all
members of the friend class may access all private members of the class
declaring the friend. As the friend class only needs to be declared, the
organization of the declaration is much easier than when template functions
are declared as friends. In the following example a class <code>Iterator</code> is
declared as a friend of a class <code>Dictionary</code>. Thus, the <code>Iterator</code> is able
to access <code>Dictionary</code>'s private data. There are some interesting points to
note here:
        <ul>
        <li> To declare a template class as a friend, that class is
simply declared as a template class before it is declared as a friend:
                    <pre>
    template &lt;typename Key, typename Value&gt;
    class Iterator;

    template &lt;typename Key, typename Value&gt;
    class Dictionary
    {
        friend class Iterator&lt;Key, Value&gt;;
</pre>
<p>
<li> However, the friend class'ss interface may already be used, even
before the compiler has seen the friend's interface:
                    <pre>
    template &lt;typename Key, typename Value&gt;
    template &lt;typename Key2, typename Value2&gt;
    Iterator&lt;Key2, Value2&gt; Dictionary&lt;Key, Value&gt;::begin()
    {
        return Iterator&lt;Key, Value&gt;(*this);
    }
    template &lt;typename Key, typename Value&gt;
    template &lt;typename Key2, typename Value2&gt;
    Iterator&lt;Key2, Value2&gt; Dictionary&lt;Key, Value&gt;::subset(Key const &amp;key)
    {
        return Iterator&lt;Key, Value&gt;(*this).subset(key);
    }
</pre>
<p>
<li> Of course, the friend's interface must still be seen by the
compiler. Since it's a support class for <code>Dictionary</code>, it can safely define
a <code>std::map</code> data member, which is initialized by its constructor, accessing
the <code>Dictionary</code>'s private data member <code>d_dict</code>:
                    <pre>
    template &lt;typename Key, typename Value&gt;
    class Iterator
    {
        std::map&lt;Key, Value&gt; &amp;d_dict;

        public:
            Iterator(Dictionary&lt;Key, Value&gt; &amp;dict)
            :
                d_dict(dict.d_dict)
            {}
</pre>
<p>
<li> The <code>Iterator</code> member <code>begin()</code> simply returns a <code>map</code>
iterator. However, since it is not known to the compiler what the
instantiation of the map will look like, a <code>map&lt;Key, Value&gt;::iterator</code>
is a (deprecated) <a name="an2725"></a>
<em>implicit typename</em>. To make it an <em>explicit</em> typename,
simply prefix <code>typename</code> to <code>begin()</code>'s return type:
            <a name="an2726"></a>

                    <pre>
    template &lt;typename Key, typename Value&gt;
    typename std::map&lt;Key, Value&gt;::iterator Iterator&lt;Key, Value&gt;::begin()
    {
        return d_dict.begin();
    }
</pre>
<p>
</ul>
    <li> In the previous example we might decide that only a <code>Dictionary</code>
should be able to construct an <code>Iterator</code>, as <code>Iterator</code> is closely tied
to <code>Dictionary</code>. This can be realized by defining <code>Iterator</code>'s constructor
in its private section, and declaring <code>Dictionary Iterator</code>'s
friend. Consequently, only <code>Dictionary</code> can create its own <code>Iterator</code>. By
declaring <code>Iterator</code>'s constructor as a <em>bound</em> friend, we ensure that it
can only create <code>Iterator</code>s using template parameters identical to its
own. Here is how it's realized:
                <pre>
    template &lt;typename Key, typename Value&gt;
    class Iterator
    {
        friend Dictionary&lt;Key, Value&gt;::Dictionary();

        std::map&lt;Key, Value&gt; &amp;d_dict;

        Iterator(Dictionary&lt;Key, Value&gt; &amp;dict);

        public:
</pre>
<p>
In this example, <code>Dictionary</code>'s constructor is defined as <code>Iterator</code>'s
friend. Here the friend is a template member. Other members can be declared as
a class's friend as well, in which case their prototypes must be used,
including the types of their return values. So, assuming that
        <pre>
        std::vector&lt;Value&gt; sortValues()
</pre>
    is a member of <code>Dictionary</code>, returning a sorted vector of its values,
then the corresponding bound friend declaration would be:
        <pre>
    friend std::vector&lt;Value&gt; Dictionary&lt;Key, Value&gt;::sortValues();
</pre>
    </ul>
    Finally, the following basic example can be used as a prototype for
situations where bound friends are useful:
        <pre>
    template &lt;typename T&gt;           // a function
    void fun(T *t)                  // template
    {
        t-&gt;not_public();
    };

    template &lt;typename X&gt;           // a template class
    class A
    {                               // fun() is used as
                                    // friend bound to A,
                                    // instantiated for X,
                                    // whatever X may be
        friend void fun&lt;A&lt;X&gt; &gt;(A&lt;X&gt; *);

        public:
            A();

        private:
            void not_public();
    };

    template &lt;typename X&gt;
    A&lt;X&gt;::A()
    {
        fun(this);
    }

    template &lt;typename X&gt;
    void A&lt;X&gt;::not_public()
    {}

    int main()
    {
        A&lt;int&gt; a;

        fun(&amp;a);                    // fun instantiated for
                                    // A&lt;int&gt;.
    }
</pre>
<p>
<a name="l351"></a>
<h3>19.8.3: Unbound templates as friends</h3>
    <a name="templateclasses/unboundfriends"></a>    When a friend is declared as an <em>unbound</em> friend, it merely declares an
existing template to be its friend, no matter how it is instantiated. This may
be useful in situations where the friend should be able to
instantiate objects of template classes declaring the friend, allowing the
friend to access the instantiated object's private members.
Again, functions, classes and member functions may be declared as unbound
friends.
<p>
Here are  the syntactical conventions  declaring unbound friends:
    <ul>
        <li> Declaring an unbound template function as a friend: any
instantiation of the template function may instantiate objects of the template
class and may access its private members. Assume the following
template function has been defined
        <pre>
    template &lt;typename Iterator, typename Class, typename Data&gt;
    Class &amp;ForEach(Iterator begin, Iterator end, Class &amp;object,
                        void (Class::*member)(Data &amp;));
</pre>
<p>
This template function can be declared as an unbound friend in the
following template class <code>Vector2</code>:
        <pre>
    template &lt;typename Type&gt;
    class Vector2: public std::vector&lt;std::vector&lt;Type&gt; &gt;
    {
        template &lt;typename Iterator, typename Class, typename Data&gt;
        friend Class &amp;ForEach(Iterator begin, Iterator end, Class &amp;object,
                    void (Class::*member)(Data &amp;));
        ...
    };
</pre>
    If the template function is defined inside some namespace, the namespace
must be mentioned as well. E.g., assuming that <code>ForEach()</code> is defined in the
namespace <code>FBB</code> its friend declaration becomes:
        <pre>
    template &lt;typename Iterator, typename Class, typename Data&gt;
    friend Class &amp;FBB::ForEach(Iterator begin, Iterator end, Class &amp;object,
                    void (Class::*member)(Data &amp;));
</pre>
    The following example illustrates the use of an unbound friend. The class
<code>Vector2</code> stores vectors of elements of template type parameter
<code>Type</code>. Its <code>process()</code> member uses <code>ForEach()</code> to have its private
<code>rows()</code> member called, which in turn uses <code>ForEach()</code> to call its private
<code>columns()</code> member. Consequently, <code>Vector2</code> uses two instantiations of
<code>ForEach()</code>, and therefore an unbound friend is appropriate here. It is
assumed that <code>Type</code> class objects can be inserted into <code>ostream</code> objects
(the definition of the <code>ForEach()</code> template function can be found in the
<code>cplusplus.yo.zip</code> archive at the <code>ftp.rug.nl</code> ftp-server). Here is the
program:
                <pre>
    template &lt;typename Type&gt;
    class Vector2: public std::vector&lt;std::vector&lt;Type&gt; &gt;
    {
        typedef typename Vector2&lt;Type&gt;::iterator iterator;

        template &lt;typename Iterator, typename Class, typename Data&gt;
        friend Class &amp;ForEach(Iterator begin, Iterator end, Class &amp;object,
                    void (Class::*member)(Data &amp;));
        public:
            void process();

        private:
            void rows(std::vector&lt;Type&gt; &amp;row);
            void columns(Type &amp;str);
    };

    template &lt;typename Type&gt;
    void Vector2&lt;Type&gt;::process()
    {
        ForEach&lt;iterator, Vector2&lt;Type&gt;, std::vector&lt;Type&gt; &gt;
                (this-&gt;begin(), this-&gt;end(), *this, &amp;Vector2&lt;Type&gt;::rows);
    }

    template &lt;typename Type&gt;
    void Vector2&lt;Type&gt;::rows(std::vector&lt;Type&gt; &amp;row)
    {
        ForEach(row.begin(), row.end(), *this,
                                        &amp;Vector2&lt;Type&gt;::columns);
        std::cout &lt;&lt; std::endl;
    }

    template &lt;typename Type&gt;
    void Vector2&lt;Type&gt;::columns(Type &amp;str)
    {
        std::cout &lt;&lt; str &lt;&lt; " ";
    }

    using namespace std;

    int main()
    {
        Vector2&lt;string&gt; c;
        c.push_back(vector&lt;string&gt;(3, "Hello"));
        c.push_back(vector&lt;string&gt;(2, "World"));

        c.process();
    }
    /*
        Generated output:

        Hello Hello Hello
        World World
    */
</pre>
<p>
<li> Analogously, a full template class may be declared as a friend. This
allows all instantiations of the friend's member functions to instantiate the
template declaring the friend class. In this case, the class declaring the
friend should offer useful functionality to different instantiations (i.e.,
using different arguments for its template parameters) of its friend
class. The syntactical convention is comparable to the convention used when
declaring an unbound friend template function:
        <pre>
    template &lt;typename Type&gt;
    class PtrVector
    {
        template &lt;typename Iterator, typename Class&gt;
        friend class Wrapper;      // unbound friend class
    };
</pre>
    All members of the template class <code>Wrapper</code> may now instantiate
<code>PtrVector</code>s using any actual type for its <code>Type</code> template parameter, at
the same time allowing <code>Wrapper</code>'s instantiation to access all of
<code>PtrVector</code>'s private members.
    <li> When only some members of a template class need access to the private
members of another template class (e.g., the other template class has private
constructors, and only some members of the first template class
need to instantiate objects of the second template class), then the latter
template class may declare only those members of the former template class
requiring access to its private members as its friends. Again, the friend
class's interface may be left unspecified. However, the compiler must be
informed that the friend member's class is indeed a class. A forward
declaration of that class must therefore be given as well. In the following
example <code>PtrVector</code> declares <code>Wrapper::begin()</code> as its friend. Note the
forward declaration of the class <code>Wrapper</code>:
        <pre>
    template &lt;typename Iterator&gt;
    class Wrapper;

    template &lt;typename Type&gt;
    class PtrVector
    {
        template &lt;typename Iterator&gt; friend
            PtrVector&lt;Type&gt; Wrapper&lt;Iterator&gt;::begin(Iterator const &amp;t1);
        ...
    };
</pre>
    </ul>
<p>
<a name="DERIVEDTEMPCLASS"></a><a name="l352"></a>
<h2>19.9: Template class derivation</h2>
<a name="templateclasses/derived"></a>        Template classes can be used in <a name="an2727"></a>
class derivation as well. When a
template class is used in class derivation, the following situations should be
distinguished:
    <ul>
    <li> An existing template class is used as base class when deriving
a concrete class. In this case, the resulting class is still partially a
template class, but this is somewhat hidden from view when an object of the
derived class is constructed.
    <li> An existing template class is used as the base class when deriving
another template class. Here the template-class characteristics remain clearly
visible.
    <li> A concrete class is used as the base class when deriving a template
class. This interesting hybrid allows us to construct template classes that
        <a name="an2728"></a>

are <em>partially precompiled</em>.
    </ul>
    These three variants of <a name="an2729"></a>
template class derivation will now be
elaborated.
<p>
Consider the following base class:
        <pre>
    template&lt;typename T&gt;
    class Base
    {
        T const &amp;t;

        public:
            Base(T const &amp;t);
    };
</pre>
    The above class is a template class, which can be used as a <a name="an2730"></a>
base class
for the following <a name="an2731"></a>
derived template class <code>Derived</code>:
        <pre>
    template&lt;typename T&gt;
    class Derived: public Base&lt;T&gt;
    {
        public:
            Derived(T const &amp;t);
    };

    template&lt;typename T&gt;
    Derived&lt;T&gt;::Derived(T const &amp;t)
    :
        Base(t)
    {}
</pre>
    Other combinations are possible as well: by specifying concrete template
type parameters of the base class, the base class is instantiated and the
derived class becomes an ordinary (non-template) class:
        <pre>
    class Ordinary: public Base&lt;int&gt;
    {
        public:
            Ordinary(int x);
    };

    inline Ordinary::Ordinary(int x)
    :
        Base(x)
    {}

    // With the following object definition:
    Ordinary
        o(5);
</pre>
    This construction allows us in a specific situation to
    <a name="an2732"></a>
add functionality to a template class, without the need for
constructing a derived template class.
<p>
Template class derivation pretty much follows the same rules as ordinary
class derivation, not involving template classes. However, some subtleties
associated with template class derivation may easily cause confusion. In the
following sections class derivation involving template classes will be
discussed. Some of the examples shown in these sections may contain unexpected
statements and expressions, like the use of <code>this</code> when members of a
template base class are called from a derived class. The `chicken and egg'
problem I encountered here was solved by first discussing the principles of
template class derivation; following that discussion the subtleties that are
part of template class derivation are discussed in section <a href="cplusplus19.html#SUBTLETIES">19.11</a>.
<p>
<a name="l353"></a>
<h3>19.9.1: Deriving non-template classes from template classes</h3>
    <a name="templateclasses/template2concrete"></a>When an existing template class is used as a base class for deriving a
non-template (concrete) class, the template class parameters are specified
when defining the derived class's interface.  If in a certain context an
existing template class lacks a particular functionality, then it may be
useful to derive a concrete class from a template class. For example, although
the class <code>map</code> can easily be used in combination with the <code>find_if()</code>
generic algorithm (section <a href="cplusplus17.html#FINDIF">17.4.16</a>) to locate a particular element, it
requires the construction of a class and at least two additional function
objects of that class. If this is considered too much overhead in a particular
context, extending a template class with some tailor-made functionality might
be considered.
<p>
A program executing commands entered at the keyboard might accept all unique
initial abbreviations of the commands it defines. E.g., the command <code>list</code>
might be entered as <code>l, li, lis</code> or <code>list</code>. By deriving a class
<code>Handler</code> from
        <pre>
        map&lt;string, void (Handler::*)(string const &amp;cmd)&gt;
</pre>
    and defining a <code>process(string const &amp;cmd)</code> to do the actual command
processing, the program might simply execute the following <code>main()</code>
function:
                <pre>
    int main()
    {
        string line;
        Handler cmd;

        while (getline(cin, line))
            cmd.process(line);
    }
</pre>
<p>
The class <code>Handler</code> itself is derived from a complex <code>map</code>, in which
the map's values are pointers to <code>Handler</code>'s member functions, expecting the
command line entered by the user. Here are <code>Handler</code>'s characteristics:
    <ul>
    <li> The class is derived from a <code>std::map</code>, expecting the command
associated with each command-processing member as its keys. Since
<code>Handler</code> uses the map merely to define associations between
        <a name="an2733"></a>

the commands and the processing member functions, we use private derivation
here:
                <pre>
    class Handler: private std::map&lt;std::string,
                            void (Handler::*)(std::string const &amp;cmd)&gt;
</pre>
<p>
<li> The actual association can be defined using static private data
members: <code>s_cmds</code> is an array of <code>Handler::value_type</code> values, and
<code>s_cmds_end</code> is a constant pointer pointing beyond the array's last element:
                <pre>
        static value_type s_cmds[];
        static value_type *const s_cmds_end;
</pre>
<p>
<li> The constructor simply initializes the map from these two static data
members. It could be implemented inline:
                <pre>
    inline Handler::Handler()
    :
        std::map&lt;std::string,
                    void (Handler::*)(std::string const &amp;cmd)&gt;
        (s_cmds, s_cmds_end)
    {}
</pre>
<p>
<li> The member <code>process()</code> iterates along the map's elements. Once the
first word on the command line matches the initial characters of the command,
the corresponding command is executed. If no such command is found, an error
message is issued:
                <pre>
    void Handler::process(std::string const &amp;line)
    {
        istringstream istr(line);
        string cmd;
        istr &gt;&gt; cmd;
        for (iterator it = begin(); it != end(); it++)
        {
            if (it-&gt;first.find(cmd) == 0)
            {
                (this-&gt;*it-&gt;second)(line);
                return;
            }
        }
        cout &lt;&lt; "Unknown command: " &lt;&lt; line &lt;&lt; endl;
    }
</pre>
<p>
</ul>
<p>
<a name="l354"></a>
<h3>19.9.2: Deriving template classes from template classes</h3>
    <a name="templateclasses/template2template"></a>    Although it's perfectly acceptable to derive a concrete class from a
template class, the resulting class of course has limited generality compared
to its template base class. If generality is important, it's probably a better
idea to derive a template class from a template class. This allows us the
extend an existing template class with some additional functionality, like
allowing hierarchical sorting of its elements.
<p>
The following class <code>SortVector</code> is a template class derived from the
existing template class <code>Vector</code>. However, it allows us to perform a
<a name="an2734"></a>
<em>hierarchical sort</em> of its elements, using any order of any members its
data elements may contain. To accomplish this there is but one requirement:
the <code>SortVector</code>'s data type must have dedicated member functions comparing
its members. For example, if <code>SortVector</code>'s data type is an object of class
<code>MultiData</code>, then <code>MultiData</code> should implement member functions having the
following prototypes for each of its data members which can be compared:
        <pre>
        bool (MultiData::*)(MultiData const &amp;rhv)
</pre>
    So, if <code>MultiData</code> has two data members, <code>int d_value</code> and
<code>std::string d_text</code>, and both may be required for a hierarchical sort, then
<code>MultiData</code> should offer members like:
        <pre>
    bool intCmp(MultiData const &amp;rhv);  // returns d_value &lt; rhv.d_value
    bool textCmp(MultiData const &amp;rhv); // returns d_text  &lt; rhv.d_text
</pre>
    Furthermore, as a convenience it is also assumed that <code>operator</code><<<code>()</code> and
<code>operator</code>>><code>()</code> have been defined for <code>MultiData</code> objects, but that assumption as
such is irrelevant to the current discussion.
<p>
The template class <code>SortVector</code> is derived directly from the template
class <code>std::vector</code>. Our implementation inherits all members from that base
class, as well as two simple constructors:
                <pre>
    template &lt;typename Type&gt;
    class SortVector: public std::vector&lt;Type&gt;
    {
        public:
            SortVector()
            {}
            SortVector(Type const *begin, Type const *end)
            :
                std::vector&lt;Type&gt;(begin, end)
            {}
</pre>
<p>
However, its member <code>hierarchicalSort()</code> is the actual reason why the
class exists. This class defines the <a name="an2735"></a>
hierarchical sort criteria. It expects
        <a name="an2736"></a>

    an array of pointers to member functions of the class indicated by
<code>sortVector</code>'s template <code>Type</code> parameter as well as an <code>size_t</code>
indicating the size of the array. The array's first element indicates the
class's most significant or first sort criterion, the array's last element
indicates the class's least significant or last sort criterion. Since the
<a name="an2737"></a>
<code>stable_sort()</code> generic algorithm was designed explicitly to support
hierarchical sorting, the member uses this generic algorithm to sort
<code>SortVector</code>'s elements. With hierarchical sorting, the least significant
criterion should be sorted first. <code>hierarchicalSort()</code>'s implementation
therefore, is easy, assuming the existence of a support class <code>SortWith</code>
whose objects are initialized by the addresses of the member functions passed
to the <code>hierarchicalSort()</code> member:
                <pre>
    template &lt;typename Type&gt;
    class SortWith
    {
       bool (Type::*d_ptr)(Type const &amp;rhv) const;
</pre>
<p>
The class <code>SortWith</code> is a simple <a name="an2738"></a>
<em>wrapper class</em> around a pointer to
a predicate function. Since it's dependent on <code>SortVector</code>'s actual data
type <code>SortWith</code> itself is also a template class:
                <pre>
    template &lt;typename Type&gt;
    class SortWith
    {
       bool (Type::*d_ptr)(Type const &amp;rhv) const;
</pre>
<p>
It's constructor receives such a pointer and initializes the class's <code>d_ptr</code>
data member:
                <pre>
    template &lt;typename Type&gt;
    SortWith&lt;Type&gt;::SortWith(bool (Type::*ptr)(Type const &amp;rhv) const)
    :
        d_ptr(ptr)
    {}
</pre>
<p>
Its binary predicate member <code>operator()()</code> should return <code>true</code> if its
first argument should be sorted before its second argument:
                <pre>
    template &lt;typename Type&gt;
    bool SortWith&lt;Type&gt;::operator()(Type const &amp;lhv, Type const &amp;rhv) const
    {
        return (lhv.*d_ptr)(rhv);
    }
</pre>
<p>
Finally, an illustration is provided by the following <code>main()</code> function.
    <ul>
    <li> First, A <code>SortVector</code> object is created for <code>MultiData</code> objects,
using the <a name="an2739"></a>
<code>copy()</code> generic algorithm to fill the <code>SortVector</code> object from
information appearing at the program's standard input stream. Having
initialized the object its elements are displayed to the standard output
stream:
                <pre>
        SortVector&lt;MultiData&gt; sv;

        copy(istream_iterator&lt;MultiData&gt;(cin),
                istream_iterator&lt;MultiData&gt;(),
                back_inserter(sv));
</pre>
<p>
<li> An array of pointers to members is initialized with the addresses of
two member functions. The text comparison is considered the most significant
sort criterion:
                <pre>
        bool (MultiData::*arr[])(MultiData const &amp;rhv) const =
        {
            &amp;MultiData::textCmp,
            &amp;MultiData::intCmp,
        };
</pre>
<p>
<li> Next, the array's elements are sorted and displayed to the standard
output stream:
                <pre>
        sv.hierarchicalSort(arr, 2);
</pre>
<p>
<li> Then the two elements of the array of pointers to <code>MultiData</code>'s
member functions are swapped, and the previous step is repeated:
                <pre>
        swap(arr[0], arr[1]);
        sv.hierarchicalSort(arr, 2);
</pre>
<p>
</ul>
    After compilation the program the following command can be given:
        <pre>
        echo a 1 b 2 a 2 b 1 | a.out
</pre>
    This results in the following output:
        <pre>
    a 1 b 2 a 2 b 1
    ====
    a 1 a 2 b 1 b 2
    ====
    a 1 b 1 a 2 b 2
    ====
</pre>
<p>
<a name="TFROMC"></a><a name="l355"></a>
<h3>19.9.3: Deriving template classes from non-template classes</h3>
    <a name="templateclasses/concrete2template"></a>    An existing class may be used as the base class for deriving a template
        <a name="an2740"></a>

class. The advantage of such an inheritance tree is that the base class's
members may all be compiled beforehand, so when objects of the template class
are instantiated only the used members of the derived (template) class need to
be instantiated.
<p>
This approach may be used for all template classes having member functions
whose implementations do not depend on template parameters. These members may
be defined in a separate class which is then used as a base class of the
template class derived from it.
<p>
As an illustration of this approach we'll develop such a template class in
this section. We'll develop a class <code>Table</code> derived from a non-template
class <code>TableType</code>. The class <code>Table</code> will display elements of some type in
a table having a configurable number of columns. The elements are either
displayed horizontally (the first <em>k</em> elements occupying the first row) or
vertically (the first <em>r</em> elements occupying a first column).
<p>
When displaying the table's elements they are inserted into a stream. This
allows us to define the handling of the table in a separate class
(<code>TableType</code>), implementing the table's presentation. Since the table's
elements are inserted into a stream, the conversion to text (or <code>string</code>)
can be implemented in <code>Table</code>, but the handling of the strings is left to
<code>TableType</code>. We'll cover some characteristics of <code>TableType</code> shortly,
concentrating on <code>Table</code>'s interface first:
    <ul>
    <li> The class <code>Table</code> is a template class, requiring only one template
type parameter: <code>Iterator</code> refers to an iterator to some data type:
                <pre>
template &lt;typename Iterator&gt;
class Table: public TableType
{
</pre>
<p>
<li> It requires no data members: all data manipulations are performed by
<code>TableType</code>.
    <li> It has two constructors. The constructor's first two parameters are
<code>Iterator</code>s used to iterate over the elements to enter into the
table. Furthermore, the constructors require us to specify the number of
columns we would like our table to have, as well as a
<em>FillDirection</em>. <code>FillDirection</code> is an <code>enum</code> type that is actually
defined by <code>TableType</code>, having values <code>Horizontal</code> and <code>Vertical</code>. To
allow <code>Table</code>'s users to exercise control over headers, footers,
captions, horizontal and vertical separators, one constructor has
<code>TableSupport</code> reference parameter. The class <code>TableSupport</code> will be
developed later as a virtual class allowing clients to exercise this
control. Here are the class's constructors:
                <pre>
        Table(Iterator const &amp;begin, Iterator const &amp;end,
                size_t nColumns, FillDirection direction);
        Table(Iterator const &amp;begin, Iterator const &amp;end,
                TableSupport &amp;tableSupport,
                size_t nColumns, FillDirection direction);
</pre>
<p>
<li> The constructors are <code>Table</code>'s only two public members. Both
constructors use a base class initializer to initialize their <code>TableType</code>
base class and then call the class's private member <code>fill()</code> to insert data
into the <code>TableType</code> base class object. Here are the constructor's
implementations:
                <pre>
template &lt;typename Iterator&gt;
Table&lt;Iterator&gt;::Table(Iterator const &amp;begin, Iterator const &amp;end,
                TableSupport &amp;tableSupport,
                size_t nColumns, FillDirection direction)
:
    TableType(tableSupport, nColumns, direction)
{
    fill(begin, end);
}

template &lt;typename Iterator&gt;
Table&lt;Iterator&gt;::Table(Iterator const &amp;begin, Iterator const &amp;end,
                size_t nColumns, FillDirection direction)
:
    TableType(nColumns, direction)
{
    fill(begin, end);
}
</pre>
<p>
<li> The class's <code>fill()</code> member iterates over the range of elements
<code>[begin, end)</code>, as defined by the constructor's first two parameters.
As we will see shortly, <code>TableType</code> defines a protected data member
<code>std::vector&lt;std::string&gt; d_string</code>. One of the requirements of the data
type to which the iterators point is that this data type can be inserted into
streams. So, <code>fill()</code> uses a <code>ostringstream</code> object to obtain the textual
representation of the data, which is then appended to <code>d_string</code>:
                <pre>
template &lt;typename Iterator&gt;
void Table&lt;Iterator&gt;::fill(Iterator it, Iterator const &amp;end)
{
    while (it != end)
    {
        std::ostringstream str;
        str &lt;&lt; *it++;
        d_string.push_back(str.str());
    }
    init();
}
</pre>
<p>
</ul>
    This completes the implementation of the class <code>Table</code>. Note that this
template class only has three members, two of them constructors. Therefore, in
most cases only two template functions will have to be instantiated: a
constructor and the class's <code>fill()</code> member. For example, the following
constructs a table having four columns, vertically filled by <code>string</code>s
extracted from the standard input stream:
        <pre>
    Table&lt;istream_iterator&lt;string&gt; &gt;
        table(istream_iterator&lt;string&gt;(cin), istream_iterator&lt;string&gt;(),
              4, TableType::Vertical);
</pre>
    Note here that the fill-direction is specified as
<code>TableType::Vertical</code>. It could also have been specified using <code>Table</code>,
but since <code>Table</code> is a template class, the specification would become
somewhat more complex: <code>Table&lt;istream_iterator&lt;string&gt; &gt;::Vertical</code>.
<p>
Now that the <code>Table</code> derived class has been designed, let's turn our
attention to the class <code>TableType</code>. Here are its essential characteristics:
    <ul>
    <li> It is a concrete class, designed to operate as <code>Table</code>'s base
class.
    <li> It uses various private data members, among which <code>d_colWidth</code>, a
vector storing the width of the widest element per column and <code>d_indexFun</code>,
pointing to the class's member function returning the element in
<code>table[row][column]</code>, conditional to the table's fill
direction. <code>TableType</code> also uses a <code>TableSupport</code> pointer and a
reference. The constructor not requiring a <code>TableSupport</code> object uses the
<code>TableSupport *</code> to allocate a (default) <code>TableSupport</code> object and then
uses the <code>TableSupport &amp;</code> as the object's alias. The other constructor
initializes the pointer to 0, and uses the reference data member to refer to
the <code>TableSupport</code> object provided by its parameter. Alternatively, a static
<code>TableSupport</code> object might have been used to initialize the reference data
member in the former constructor. The remaining private data members are
probably self-explanatory:
                <pre>
        TableSupport           *d_tableSupportPtr;
        TableSupport           &amp;d_tableSupport;
        size_t                d_maxWidth;
        size_t                d_nRows;
        size_t                d_nColumns;
        WidthType               d_widthType;
        std::vector&lt;size_t&gt;   d_colWidth;
        size_t               (TableType::*d_widthFun)
                                        (size_t col) const;
        std::string const     &amp;(TableType::*d_indexFun)
                                        (size_t row, size_t col) const;
</pre>
<p>
<li> The actual <code>string</code> objects populating the table are stored in a
protected data member:
                <pre>
        std::vector&lt;std::string&gt; d_string;
</pre>
<p>
<li> The (protected) constructors perform basic tasks: they initialize the
object's data members. Here is the constructor expecting a reference to a
<code>TableSupport</code> object:
        <pre>
#include "tabletype.ih"

TableType::TableType(TableSupport &amp;tableSupport, size_t nColumns,
                        FillDirection direction)
:
    d_tableSupportPtr(0),
    d_tableSupport(tableSupport),
    d_maxWidth(0),
    d_nRows(0),
    d_nColumns(nColumns),
    d_widthType(ColumnWidth),
    d_colWidth(nColumns),
    d_widthFun(&amp;TableType::columnWidth),
    d_indexFun(direction == Horizontal ?
                    &amp;TableType::hIndex
                :
                    &amp;TableType::vIndex)
{}
</pre>
    <li> Once <code>d_string</code> has been filled, the table is initialized by
<code>Table::fill()</code>. The <code>init()</code> protected member resizes <code>d_string</code> so
that its size is exactly <code>rows x columns</code>, and it determines the maximum
width of the elements per column. Its implementation is straightforward:
        <pre>
#include "tabletype.ih"

void TableType::init()
{
    if (!d_string.size())                   // no elements
        return;                             // then do nothing

    d_nRows = (d_string.size() + d_nColumns - 1) / d_nColumns;
    d_string.resize(d_nRows * d_nColumns);  // enforce complete table

                                            // determine max width per column,
                                            // and max column width
    for (size_t col = 0; col &lt; d_nColumns; col++)
    {
        size_t width = 0;
        for (size_t row = 0; row &lt; d_nRows; row++)
        {
            size_t len = stringAt(row, col).length();
            if (width &lt; len)
                width = len;
        }
        d_colWidth[col] = width;

        if (d_maxWidth &lt; width)             // max. width so far.
            d_maxWidth = width;
    }
}
</pre>
    <li> The public member <code>insert()</code> is used by the insertion operator
(<code>operator</code><<<code>()</code>) to insert a <code>Table</code> into a stream. First it informs the
<code>TableSupport</code> object about the table's dimensions. Next it displays the
table, allowing the <code>TableSupport</code> object to write headers, footers and
separators:
        <pre>
#include "tabletype.ih"

ostream &amp;TableType::insert(ostream &amp;ostr) const
{
    if (!d_nRows)
        return ostr;

    d_tableSupport.setParam(ostr, d_nRows, d_colWidth,
                            d_widthType == EqualWidth ? d_maxWidth : 0);

    for (size_t row = 0; row &lt; d_nRows; row++)
    {
        d_tableSupport.hline(row);

        for (size_t col = 0; col &lt; d_nColumns; col++)
        {
            size_t colwidth = width(col);

            d_tableSupport.vline(col);
            ostr &lt;&lt; setw(colwidth) &lt;&lt; stringAt(row, col);
        }

        d_tableSupport.vline();
    }
    d_tableSupport.hline();

    return ostr;
}
</pre>
    <li> The <code>cplusplus.yo.zip</code> archive contains <code>TableSupport</code>'s full
implementation. This implementation is found in the directory
<code>yo/templateclasses/examples/table</code>. Most of its remaining members are
private. Among those, the following two members return table element
<code>[row][column]</code> for, respectively, a horizontally filled table and a
vertically filled table:
              <pre>
    inline std::string const &amp;TableType::hIndex(size_t row, size_t col) const
    {
        return d_string[row * d_nColumns + col];
    }
    inline std::string const &amp;TableType::vIndex(size_t row, size_t col) const
    {
        return d_string[col * d_nRows + row];
    }
</pre>
<p>
</ul>
<p>
The support class <code>TableSupport</code> is used to display headers, footers,
captions and separators. It has four virtual members to perform those tasks
(and, of course, a virtual constructor):
    <ul>
    <li><code>hline(size_t rowIndex)</code>: called just before the elements in row
<code>rowIndex</code> will be displayed.
    <li><code>hline()</code>: called immediately after displaying the final row.
    <li><code>vline(size_t colIndex)</code>: called just before the element in column
<code>colIndex</code> will be displayed.
    <li><code>vline()</code>: called immediately after displaying all elements in a row.
    </ul>
    The reader is referrred to the <code>cplusplus.yo.zip</code> archive for the full
implementation of the classes <code>Table</code>, <code>TableType</code> and <code>TableSupport</code>.
Here is a small program showing their use:
    <pre>
    /*
                                  table.cc
    */

    #include &lt;fstream&gt;
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &lt;iterator&gt;
    #include &lt;sstream&gt;

    #include "tablesupport/tablesupport.h"
    #include "table/table.h"

    using namespace std;
    using namespace FBB;

    int main(int argc, char **argv)
    {
        size_t nCols = 5;
        if (argc &gt; 1)
        {
            istringstream iss(argv[1]);
            iss &gt;&gt; nCols;
        }

        istream_iterator&lt;string&gt;   iter(cin);   // first iterator isn't const

        Table&lt;istream_iterator&lt;string&gt; &gt;
            table(iter, istream_iterator&lt;string&gt;(), nCols,
                  argc == 2 ? TableType::Vertical : TableType::Horizontal);

        cout &lt;&lt; table &lt;&lt; endl;
        return 0;
    }
    /*
        Example of generated output:
        After: echo a b c d e f g h i j | demo 3
            a e i
            b f j
            c g
            d h
        After: echo a b c d e f g h i j | demo 3 h
            a b c
            d e f
            g h i
            j
    */
</pre>
<p>
<a name="l356"></a>
<h2>19.10: Template classes and nesting</h2>
<a name="templateclasses/nesting"></a>When a class is nested within a template class, it automatically becomes a
template class itself.
        <a name="an2741"></a>

    The <a name="an2742"></a>
nested class may use the template parameters of the surrounding
class, as shown in the following skeleton program. Within a class
<code>PtrVector</code>, a class <code>iterator</code> is defined. The nested class receives its
information from its surrounding class, a <code>PtrVector&lt;Type&gt;</code> class. Since
this surrounding class should be the only class constructing its iterators,
<code>iterator</code>'s constructor is made <a name="an2743"></a>
private, and the surrounding class is
given access to the private members of <code>iterator</code> using a
        <a name="an2744"></a>
<em>bound friend</em> declaration.
    Here is the initial section of <code>PtrVector</code>'s class interface:
                <pre>
    template &lt;typename Type&gt;
    class PtrVector: public std::vector&lt;Type *&gt;
</pre>
<p>
This shows that the <code>std::vector</code> base class will store pointers to
<code>Type</code> values, rather than the values themselves. Of course, a destructor is
needed now, since the (externally allocated) memory for the <code>Type</code> objects
must eventually be freed. Alternatively, the allocation might be part of
<code>PtrVector</code>'s tasks, when storing new elements. Here it is assumed that the
<code>PtrVector</code>'s clients do the required allocations, and that the destructor
will be implemented later on.
<p>
The nested class defines its constructor as a private member, and allows
<code>PtrVector&lt;Type&gt;</code> objects to access its private members. Therefore only
objects of the surrounding <code>PtrVector&lt;Type&gt;</code> class type are allowed to
construct their <code>iterator</code> objects. However, <code>PtrVector&lt;Type&gt;</code>'s clients
may construct <em>copies</em> of the <code>PtrVector&lt;Type&gt;::iterator</code> objects they
use. Here is the nested class <code>iterator</code>, containing the required <code>friend</code>
declaration. Note the use of the <code>typename</code> keyword: since
<code>std::vector&lt;Type *&gt;::iterator</code> depends on a template parameter, it is not
yet an instantiated class, so <code>iterator</code> becomes an <a name="an2745"></a>
implicit typename.
The compiler issues a corresponding warning if <code>typename</code> has been
omitted. In these cases  <code>typename</code> must be used. Here is the class
interface:
                <pre>
            class iterator
            {
                friend class PtrVector&lt;Type&gt;;
                typename std::vector&lt;Type *&gt;::iterator d_begin;

                iterator(PtrVector&lt;Type&gt; &amp;vector);

                public:
                    Type &amp;operator*();
            };
</pre>
<p>
The implementation of the members shows that the base class's <code>begin()</code>
member is called to initialize <code>d_begin</code>. Also note that the return type of
<code>PtrVector&lt;Type&gt;::begin()</code> must again be preceded by <code>typename</code>:
                <pre>
    template &lt;typename Type&gt;
    PtrVector&lt;Type&gt;::iterator::iterator(PtrVector&lt;Type&gt; &amp;vector)
    :
        d_begin(vector.std::vector&lt;Type *&gt;::begin())
    {}

    template &lt;typename Type&gt;
    Type &amp;PtrVector&lt;Type&gt;::iterator::operator*()
    {
        return **d_begin;
    }
</pre>
<p>
The remainder of the class is simple. Omitting all other functions that
might be implemented, the function <code>begin()</code> will return a newly constructed
<code>PtrVector&lt;Type&gt;::iterator</code> object. It may call the constructor since the
class <code>iterator</code> called its surrounding class its friend:
                <pre>
    template &lt;typename Type&gt;
    typename PtrVector&lt;Type&gt;::iterator PtrVector&lt;Type&gt;::begin()
    {
        return iterator(*this);
    }
</pre>
<p>
Here is a simple  <a name="an2746"></a>
skeleton program, showing how the nested class
<code>iterator</code> might be used:
                <pre>
    int main()
    {
        PtrVector&lt;int&gt; vi;

        vi.push_back(new int(1234));

        PtrVector&lt;int&gt;::iterator begin = vi.begin();

        std::cout &lt;&lt; *begin &lt;&lt; endl;
    }
</pre>
<p>
Nested <a name="an2747"></a>
 enumerations and <a name="an2748"></a>

typedefs can also be defined in template classes. The class <code>Table</code>,
mentioned before (section <a href="cplusplus19.html#TFROMC">19.9.3</a>) inherited the enumeration
<code>TableType::FillDirection</code>. If <code>Table</code> would have been implemented as a
full template class, then this enumeration would have been defined in
<code>Table</code> itself as:
        <pre>
    template &lt;typename Iterator&gt;
    class Table: public TableType
    {
        public:
            enum FillDirection
            {
                Horizontal,
                Vertical
            };
        ...
    };
</pre>
    In this case, the actual value of the template type parameter must be
specified when referring to a <code>FillDirection</code> value or to its type. For
example (assuming <code>iter</code> and <code>nCols</code> are defined as in section
<a href="cplusplus19.html#TFROMC">19.9.3</a>):
        <pre>
    Table&lt;istream_iterator&lt;string&gt; &gt;::FillDirection direction =
                argc == 2 ?
                    Table&lt;istream_iterator&lt;string&gt; &gt;::Vertical
                :
                    Table&lt;istream_iterator&lt;string&gt; &gt;::Horizontal;

    Table&lt;istream_iterator&lt;string&gt; &gt;
        table(iter, istream_iterator&lt;string&gt;(), nCols, direction);
</pre>
<p>
<a name="SUBTLETIES"></a><a name="l357"></a>
<h2>19.11: Subtleties with template classes</h2>
<p>
<a name="TYPERES"></a><a name="l358"></a>
<h3>19.11.1: Type resolution for base class members</h3>
    <a name="templateclasses/basenameresolution"></a>Consider the following example of a template base and a derived class:
        <pre>
    #include &lt;iostream&gt;

    template &lt;typename T&gt;
    class Base
    {
        public:
            void member();
    };

    template &lt;typename T&gt;
    void Base&lt;T&gt;::member()
    {
        std::cout &lt;&lt; "This is Base&lt;T&gt;::member()\n";
    }

    template &lt;typename T&gt;
    class Derived: public Base&lt;T&gt;
    {
        public:
            Derived();
    };

    template &lt;typename T&gt;
    Derived&lt;T&gt;::Derived()
    {
        member();
    }
</pre>
    This example won't compile, and the compiler tells us something like:
        <a name="an2749"></a>

        <pre>
    error: there are no arguments to 'member' that depend on a template
           parameter, so a declaration of 'member' must be available
</pre>
<p>
At first glance, this error may cause some confusion, since with
non-template classes public and protected base class members are immediately
available. This holds also true for template classes, but only if the compiler
can figure out what we mean. In the above situation, the compiler can't, since
it doesn't know for what type <code>T</code> the member function <code>member</code> must be
initialized.
<p>
To appreciate why this is true, consider the situation where we have
defined a specialization:
        <pre>
    template &lt;&gt;
    Base&lt;int&gt;::member()
    {
        std::cout &lt;&lt; "This is the int-specialization\n";
    }
</pre>
    Since the compiler, when processing the class <code>Derived</code>, can't be sure
that no specialization will be in effect once an instantiation of <code>Derived</code>
is called for, it can't decide yet for what type to instantiate <code>member</code>,
since <code>member()</code>'s call in <code>Derived::Derived()</code> doesn't require a
template type parameter. In cases like these, where no template type parameter
is available to determine which type to use, the compiler must be told
that it should postpone its decision about the template type parameter to use
    <a name="an2750"></a>
 for <code>member()</code>
until instantiation time. This can be realized in two ways: either by using
<code>this</code>, or by explicitly mentioning the base class, instantiated for the
derived class's template type(s). In the following <code>main()</code> function both
forms are used. Note that with the <code>int</code> template type the <code>int</code>
specialization is used.
        <pre>
    #include &lt;iostream&gt;

    template &lt;typename T&gt;
    class Base
    {
        public:
            void member();
    };

        template &lt;typename T&gt;
        void Base&lt;T&gt;::member()
        {
            std::cout &lt;&lt; "This is Base&lt;T&gt;::member()\n";
        }

        template &lt;&gt;
        void Base&lt;int&gt;::member()
        {
            std::cout &lt;&lt; "This is the int-specialization\n";
        }

    template &lt;typename T&gt;
    class Derived: public Base&lt;T&gt;
    {
        public:
            Derived();
    };

        template &lt;typename T&gt;
        Derived&lt;T&gt;::Derived()
        {
            this-&gt;member();
            Base&lt;T&gt;::member();
        }

    int main()
    {
        Derived&lt;double&gt; d;
        Derived&lt;int&gt; i;
    }

    /*
        Generated output:
        This is Base&lt;T&gt;::member()
        This is Base&lt;T&gt;::member()
        This is the int-specialization
        This is the int-specialization
    */
</pre>
<p>
<a name="RETURNNESTED"></a><a name="l359"></a>
<h3>19.11.2: Returning types nested under template classes</h3>
    <a name="templateclasses/returnnested"></a>In section <a href="cplusplus19.html#DISTINGUISH">19.1.3</a> the keyword <code>typename</code> was introduced to allow
the compiler to distinguish between template class members and types that are
    <a name="an2751"></a>
 defined within
template classes. The <code>typename</code> keyword allows us to tell the compiler that
we have a type in mind that is nested under a template class.
<p>
Consider the following example in which a nested class, that is not
depending on a template parameter, is defined within a template
class. Furthermore, the template class member <code>nested()</code> should return an
object of the nested class. Note that in this example the (deprecated)
member implementation inside the class interface is used:
        <pre>
    template &lt;typename T&gt;
    class Outer
    {
        public:
            class Nested
            {
            };

        Nested nested() const
        {
            return Nested();
        }
    };
</pre>
    The above example compiles flawlessly: within the class <code>Outer</code> there is
no ambiguity with respect to the meaning of <code>nested()</code>'s return
type. Since it is advised to implement inline and template members below their
class interface (see section <a href="cplusplus06.html#DEFINLINE">6.3.1</a>), we now remove the implementation
from the interface itself, and put it below the interface. Suddenly the
compiler refuses to compile our member <code>nested()</code>:
        <pre>
    template &lt;typename T&gt;
    class Outer
    {
        public:
            class Nested
            {
            };

        Nested nested() const;
    };

    template &lt;typename T&gt;
    Outer&lt;T&gt;::Nested Outer&lt;T&gt;::nested() const
    {
        return Nested();
    }
</pre>
    The above implementation of <code>nested()</code> produces an error message like
<p>
<em>error:</em>
    <a name="an2752"></a>
<em>expected constructor, destructor, or type conversion</em> <em>before
'Outer'</em>.
<p>
In this case a type specification is required as <code>Outer&lt;T&gt;::Nested</code>
refers to a <em>type</em>, nested under <code>Outer&lt;T&gt;</code> rather than to a member of
<code>Outer&lt;T&gt;</code>. In situations like these, where a type that is defined as a
<a name="an2753"></a>
<em>nested type</em> in a template class is returned, the <code>typename</code> keyword must
be used to coerce the compiler into interpreting <code>Outer&lt;T&gt;::Nested</code> as a
type name. Writing <code>typename</code> in front of <code>Outer&lt;T&gt;::Nested</code> removes the
compilation error and the correct implementation of the function <code>nested()</code>
becomes:
        <pre>
    template &lt;typename T&gt;
    typename Outer&lt;T&gt;::Nested Outer&lt;T&gt;::nested() const
    {
        return Nested();
    }
</pre>
<p>
<a name="ITERATORCONS"></a><a name="l360"></a>
<h2>19.12: Constructing iterators</h2>
<a name="templateclasses/iteratorcons"></a>    In section <a href="cplusplus17.html#ITERATORS">17.2</a> the <a name="an2754"></a>
iterators used with <a name="an2755"></a>
generic algorithms
were introduced. We've seen that several types of iterators were
distinguished: <a name="an2756"></a>
InputIterators, <a name="an2757"></a>
ForwardIterators, <a name="an2758"></a>
OutputIterators,
<a name="an2759"></a>
BidirectionalIterators and <a name="an2760"></a>
RandomAccessIterators.
<p>
In section <a href="cplusplus17.html#ITERATORS">17.2</a> the <a name="an2761"></a>
characteristics of iterators were
introduced: all iterators should support an increment operation, a dereference
operation and a comparison for (in)equality.
<p>
However, when iterators must be used in the context of generic algorithms
they must meet additional requirements. This is caused by the fact that
generic algorithms check the types of the iterators they receive. Simple
pointers are usually accepted, but if an iterator-object is used it must be
able to specify the kind of iterator it represents.
<p>
To ensure that an object of a class is interpreted as a particular type of
iterator, the class must be derived from the <a name="an2762"></a>
<code>class iterator</code>. The
particular type of iterator is defined by the template class's <em>first</em>
parameter, and the particular data type to which the iterator points is
defined by the template class's <em>second</em> parameter.  Before a class may be
inherited from the class <code>iterator</code>, the following header file must have
        <a name="an2763"></a>

been included:
        <pre>
        #include &lt;iterator&gt;
</pre>
    The particular type of iterator that is implemented by the derived class
is specified using a so-called <a name="an2764"></a>
<em>iterator_tag</em>, provided as the
first template argument of the class <code>iterator</code>. For the five basic iterator
types, these tags are:
    <ul>
    <li> <a name="an2765"></a>
<code>std::input_iterator_tag</code>. This tag defines an <a name="an2766"></a>
InputIterator.
        Iterators of this type allow reading operations, iterating from
the first to the last element of the series to which the iterator refers.
    <li> <a name="an2767"></a>
<code>std::output_iterator_tag</code>. This tag defines an <a name="an2768"></a>
OutputIterator.
        Iterators of this type allow for assignment operations, iterating from
the first to the last element of the series to which the iterator refers.
    <li> <a name="an2769"></a>
<code>std::forward_iterator_tag</code>. This tag defines a
        <code>ForwardIterator</code>.
        Iterators of this type allow reading <em>and</em> assignment
operations, iterating from the first to the last element of the series to
which the iterator refers.
    <li> <a name="an2770"></a>
<code>std::bidirectional_iterator_tag</code>. This tag defines a
        <a name="an2771"></a>
BidirectionalIterator. Iterators of this type allow reading
<em>and</em> assignment operations, iterating step by step, possibly in alternating
directions, over all elements of the series to which the iterator refers.
    <li> <a name="an2772"></a>
<code>std::random_access_iterator_tag</code>. This tag defines a
    <a name="an2773"></a>
RandomAccessIterator.  Iterators of this type allow reading <em>and</em>
assignment operations, iterating, possibly in alternating directions, over all
elements of the series to which the iterator refers, using any available
(random) stepsize.
    </ul>
    Each <a name="an2774"></a>
<em>iterator tag</em> assumes that a certain set of operators is
available. The <em>RandomAccessIterator</em> is the most complex of iterators, as
it implies all other iterators.
<p>
Note that iterators are always defined over a certain range, e.g.,
<code>[begin, end)</code>. Increment and decrement operations may result in
undefined behavior of the iterator if the resulting iterator value would refer
to a location outside of this range.
<p>
Often, iterators only access the elements of the series to which they
refer. Internally, an iterator may use an ordinary pointer, but it is hardly
ever necessary for the iterator to allocate its own memory. Therefore, as the
overloaded assignment operator and the copy constructor do not have to
allocate any memory, the <em>default implementation</em> of the overloaded
assignment operator and of the copy constructor is usually sufficient. I.e.,
usually these members do not have to be implemented at all. As a consequence
there is usually also no <em>destructor</em>.
<p>
Most classes offering members returning iterators do so by having members
constructing the required iterator, which is thereupon returned as an object
by these member functions. As the <em>caller</em> of these member functions only
has to <em>use</em> or sometimes <em>copy</em> the returned iterator objects, there is
normally no need to provide any publicly available constructors, except for
the copy constructor. Therefore these constructors may usually be defined as
<em>private</em> or <em>protected</em> members. To allow an outer class to create
iterator objects, the iterator class will declare the outer class as its
<em>friend</em>.
<p>
In the following sections, the construction of a <em>RandomAccessIterator</em>,
the most complex of all iterators, and the construction of a <em>reverse
RandomAccessIterator</em> is discussed. The container class for which a random
access iterator must be developed may actually store its data elements in many
different ways, e.g., using various containers or using pointers to pointers.
Therefore it is difficult to construct a template iterator class which is
suitable for a large variety of concrete (container) classes.
<p>
In the following sections, the available <code>std::iterator</code> class will be
used to construct an inner class representing a random access iterator. This
approach clearly shows how to construct an iterator class. The reader may
either follow this approach when constructing iterator classes in other
contexts, or a full template iterator class can be designed. An example of
such a template iterator class is provided in section <a href="cplusplus20.html#CONCRETEITER">20.5</a>.
<p>
The construction of the random access iterator as shown in the next sections
aims at the realization of an iterator reaching the elements of a series of
elements only accessible through pointers. The iterator class is designed as
an inner class of a class derived from a vector of string pointers.
<p>
<a name="RANDOMIT"></a><a name="l361"></a>
<h3>19.12.1: Implementing a `RandomAccessIterator'</h3>
    <a name="templateclasses/randomiterator"></a>    When discussing containers (chapter <a href="cplusplus12.html#Containers">12</a>) it was noted that
containers own the information they contain. If they contain objects, then
these objects are destroyed once the containers are destroyed. As pointers are
no objects, and as <code>auto_ptr</code> objects cannot be stored in containers, using
pointer data types for containers was discouraged. However, we might be able
to use pointer data types in specific contexts. In the following class
<code>StringPtr</code>, a concrete class is derived from the <code>std::vector</code> container
using <code>std::string *</code> as its data type:
        <pre>
    #ifndef _INCLUDED_STRINGPTR_H_
    #define _INCLUDED_STRINGPTR_H_

    #include &lt;string&gt;
    #include &lt;vector&gt;

    class StringPtr: public std::vector&lt;std::string *&gt;
    {
        public:
            StringPtr(StringPtr const &amp;other);
            ~StringPtr();

            StringPtr &amp;operator=(StringPtr const &amp;other);
    };

    #endif
</pre>
    Note the declaration of the destructor: as the object stores string
pointers, a destructor is required to destroy the strings when the
<code>StringPtr</code> object itself is destroyed.  Similarly, a copy constructor and
overloaded assignment is required. Other members (in particular: constructors)
are not explicitly declared as they are not relevant to this section's topic.
<p>
Let's assume that we want to be able to use the <code>sort()</code> generic
algorithm with <code>StringPtr</code> objects. This algorithm (see section <a href="cplusplus17.html#SORT">17.4.58</a>)
requires two <em>RandomAccessIterators</em>. Although these iterators are available
(via <code>std::vector</code>'s <code>begin()</code> and <code>end()</code> members), they return
iterators to <code>std::string *</code>s, which cannot sensibly be compared.
<p>
To remedy this, assume that we have defined an internal type
<code>StringPtr::iterator</code>, not returning iterators to pointers, but iterators
to the objects these pointers point to. Once this <code>iterator</code> type is
available, we can add the following members to our <code>StringPtr</code> class
interface, hiding the identically named, but useless members of its base
class:
        <pre>
    StringPtr::iterator begin();    // returns iterator to the first element
    StringPtr::iterator end();      // returns iterator beyond the last
                                    // element
</pre>
    Since these two members return the (proper) iterators, the elements in a
<code>StringPtr</code> object can easily be sorted:
        <pre>
    in main()
    {
        StringPtr sp;               // assume sp is somehow filled

        sort(sp.begin(), sp.end()); // sp is now sorted
        return 0;
    }
</pre>
    To make this all work, the type <code>StringPtr::iterator</code> must be
defined. As suggested by its type name, <code>iterator</code> is a nested type of
<code>StringPtr</code>, suggesting that we may implement <code>iterator</code> as a nested class
of <code>StringPtr</code>. However, to use a <code>StringPtr::iterator</code> in combination
with the <code>sort()</code> generic algorithm, it must also be a
<a name="an2775"></a>
<code>RandomAccessIterator</code>. Therefore, <code>StringPtr::iterator</code> itself must be
derived from the existing class <a name="an2776"></a>
<code>std::iterator</code>, available once the
following preprocessor directive has been specified:
        <a name="an2777"></a>

        <pre>
        #include &lt;iterator&gt;
</pre>
    To derive a class from <code>std::iterator</code>, both the iterator type and the
data type the iterator points to must be specified. Take caution: our iterator
will take care of  the <code>string *</code> dereferencing; so the required data type
will be <code>std::string</code>, and <em>not</em> <code>std::string *</code>. So, the class
<code>iterator</code> starts its interface as:
        <pre>
    class iterator:
        public std::iterator&lt;std::random_access_iterator_tag, std::string&gt;
</pre>
    Since its base class specification is quite complex, we could consider 
associating this
type with a shorter name, using the following <code>typedef</code>:
        <pre>
    typedef std::iterator&lt;std::random_access_iterator_tag, std::string&gt;
            Iterator;
</pre>
    However, if the defined type (<code>Iterator</code>) is used only once or twice,
the typedefinition only adds clutter to the interface, and is better not used.
<p>
Now we're ready to redesign <code>StringPtr</code>'s class interface. It contains
members returning (reverse) iterators, and a nested <code>iterator</code> class. The
members will be discussed in some detail next:
                <pre>
class StringPtr: public std::vector&lt;std::string *&gt;
{
    public:
    class iterator: public
            std::iterator&lt;std::random_access_iterator_tag, std::string&gt;
    {
        friend class StringPtr;
        std::vector&lt;std::string *&gt;::iterator d_current;

        iterator(std::vector&lt;std::string *&gt;::iterator const &amp;current);

        public:
            iterator &amp;operator--();
            iterator const operator--(int);
            iterator &amp;operator++();
            bool operator==(iterator const &amp;other) const;
            bool operator!=(iterator const &amp;other) const;
            int operator-(iterator const &amp;rhs) const;
            std::string &amp;operator*() const;
            bool operator&lt;(iterator const &amp;other) const;
            iterator const operator+(int step) const;
            iterator const operator-(int step) const;
            iterator &amp;operator+=(int step); // increment over `n' steps
            iterator &amp;operator-=(int step); // decrement over `n' steps
            std::string *operator-&gt;() const;// access the fields of the
                                            // struct an iterator points
                                            // to. E.g., it-&gt;length()
    };

    typedef std::reverse_iterator&lt;iterator&gt; reverse_iterator;

    iterator begin();
    iterator end();
    reverse_iterator rbegin();
    reverse_iterator rend();
};
</pre>
<p>
Let's first have a look at <code>StringPtr::iterator</code>'s characteristics:
    <ul>
    <li> <code>iterator</code> defines <code>StringPtr</code> as its friend, so <code>iterator</code>'s
constructor can remain private: only the <code>StringPtr</code> class itself is now
able to construct <code>iterator</code>s, which seems like a sensible thing to
do. Under the current implementation, <em>copy-constructing</em> remains of course
possible. Furthermore, since an iterator is already provided by
<code>StringPtr</code>'s base class, we can use that iterator to access the information
stored in the <code>StringPtr</code> object. 
    <li> <code>StringPtr::begin()</code> and <code>StringPtr::end()</code> may simply return
<code>iterator</code> objects. Their implementations are:
                <pre>
inline StringPtr::iterator StringPtr::begin()
{
    return iterator(this-&gt;std::vector&lt;std::string *&gt;::begin());
}
inline StringPtr::iterator StringPtr::end()
{
    return iterator(this-&gt;std::vector&lt;std::string *&gt;::end());
}
</pre>
<p>
<li> All of <code>iterator</code>'s remaining members are public. It's very easy to
implement them, mainly manipulating and dereferencing the available iterator
<code>d_current</code>. A <code>RandomAccessIterator</code> (which is the most
complex of iterators) requires a series of operators. They usually
have very simple implementations, making them good candidates for
inline-members:
        <ul>
        <li><code>iterator &amp;operator++():</code> the pre-increment operator:
                    <pre>
inline StringPtr::iterator &amp;StringPtr::iterator::operator++()
{
    ++d_current;
    return *this;
}
</pre>
<p>
<li> <code>iterator &amp;</code><code>operator</code>--<code>()</code><code>:</code> the pre-decrement operator:
                    <pre>
inline StringPtr::iterator &amp;StringPtr::iterator::operator--()
{
    --d_current;
    return *this;
}
</pre>
<p>
<li> <code>iterator</code> <code>operator</code>--<code>()</code><code>:</code> the post-decrement operator:
                    <pre>
inline StringPtr::iterator const StringPtr::iterator::operator--(int)
{
    return iterator(d_current--);
}
</pre>
<p>
<li><code>iterator &amp;operator=(iterator const &amp;other):</code> the overloaded
            assignment operator. Since <code>iterator</code> objects do not allocate
            any memory themselves, the default assignment operator will do.
        <li><code>bool operator==(iterator const &amp;rhv) const:</code> testing the equality
            of two <code>iterator</code> objects:
                        <pre>
inline bool StringPtr::iterator::operator==(iterator const &amp;other) const
{
    return d_current == other.d_current;
}
</pre>
<p>
<li><code>bool operator&lt;(iterator const &amp;rhv) const:</code> tests whether the
            left-hand side iterator points to an element of the series located
            <em>before</em> the element pointed to by the right-hand side
            iterator:
                        <pre>
inline bool StringPtr::iterator::operator&lt;(iterator const &amp;other) const
{
    return **d_current &lt; **other.d_current;
}
</pre>
<p>
<li><code>int operator-(iterator const &amp;rhv) const:</code> returns the number of
            elements between the element pointed to by the left-hand side
            iterator and the right-hand side iterator (i.e., the value to add
            to the left-hand side iterator to make it equal to the value of
            the right-hand side iterator):
                        <pre>
inline int StringPtr::iterator::operator-(iterator const &amp;rhs) const
{
    return d_current - rhs.d_current;
}
</pre>
<p>
<li><code>Type &amp;operator*() const:</code> returns a reference to the object to
            which the current iterator points. With an <code>InputIterator</code> and
            with all <code>const_iterators</code>, the return type of this overloaded
            operator should be <code>Type const &amp;</code>. This operator returns a
            reference to a string. This string is obtained by dereferencing
            the dereferenced <code>d_current</code> value. As <code>d_current</code> is an
            iterator to <code>string *</code> elements, two dereference operations are
            required to reach the string itself:
                        <pre>
inline std::string &amp;StringPtr::iterator::operator*() const
{
    return **d_current;
}
</pre>
<p>
<li><code>iterator const operator+(int stepsize) const:</code> this operator
            advances the current iterator by <code>stepsize</code> steps:
                        <pre>
inline StringPtr::iterator const
        StringPtr::iterator::operator+(int step) const
{
    return iterator(d_current + step);
}
</pre>
<p>
<li><code>iterator const operator-(int stepsize) const:</code> this operator
            decreases the current iterator by <code>stepsize</code> steps:
                        <pre>
inline StringPtr::iterator const
       StringPtr::iterator::operator-(int step) const
{
    return iterator(d_current - step);
}
</pre>
<p>
<li> iterators may be constructed from
            existing iterators. This constructor doesn't have to be
            implemented, as the default copy constructor can be used.
        <li><code>std::string *operator-&gt;() const</code> is an additionally added
            operator. Here only one dereference operation is required,
            returning a pointer to the string, allowing us to access the
            members of a string via its pointer.
                        <pre>
inline std::string *StringPtr::iterator::operator-&gt;() const
{
    return *d_current;
}
</pre>
<p>
<li> Two more additionally added operators are <code>operator+=()</code> and
            <code>operator-=()</code>. They are not formally required by
            <code>RandomAccessIterators</code>, but they come in handy anyway:
                        <pre>
inline StringPtr::iterator &amp;StringPtr::iterator::operator+=(int step)
{
    d_current += step;
    return *this;
}
inline StringPtr::iterator &amp;StringPtr::iterator::operator-=(int step)
{
    d_current -= step;
    return *this;
}
</pre>
<p>
</ul>
    </ul>
    The interfaces required for other iterator types are simpler, requiring
only a subset of the interface required by a random access iterator. E.g.,
the forward iterator is never decremented and never incremented over arbitrary
step sizes. Consequently, in that case all decrement operators and
<code>operator+(int step)</code> can be omitted from the interface. Of course, the tag
to use would then be <code>std::forward_iterator_tag</code>. The tags (and the set of
required operators) varies accordingly for the other iterator types.
<p>
<a name="REVERSEIT"></a><a name="l362"></a>
<h3>19.12.2: Implementing a `reverse_iterator'</h3>
    <a name="templateclasses/reverseiterator"></a>    Once we've implemented an iterator, the matching <a name="an2778"></a>
<em>reverse iterator</em> can
be implemented in a jiffy. Comparable to the <code>std::iterator</code> a
        <a name="an2779"></a>
<code>std::reverse_iterator</code> <a name="an2780"></a>

    exists, which will nicely implement the reverse iterator for us, once we
have defined an iterator class. Its constructor merely requires an object of
the iterator type for which we want to construct a reverse iterator.
<p>
To implement a reverse iterator for <code>StringPtr</code>, we only need to define
the <code>reverse_iterator</code> type in its interface. This requires us to specify
only one line of code, which must be inserted after the interface of the class
<code>iterator</code>:
        <pre>
        typedef std::reverse_iterator&lt;iterator&gt; reverse_iterator;
</pre>
    Finally, the well known members <a name="an2781"></a>
<code>rbegin()</code> and <a name="an2782"></a>
<code>rend()</code> are added to
<code>StringPtr</code>'s interface. Again, they can easily be implemented inline:
                <pre>
inline StringPtr::reverse_iterator StringPtr::rbegin()
{
    return reverse_iterator(end());
}
inline StringPtr::reverse_iterator StringPtr::rend()
{
    return reverse_iterator(begin());
}
</pre>
<p>
Note the arguments the <code>reverse_iterator</code> constructors receive: the
        <a name="an2783"></a>

    <em>begin point</em> of the reversed iterator is obtained by providing
<code>reverse_iterator</code>'s constructor with <code>end()</code>: the <em>endpoint</em> of the
normal iterator range; the <em>endpoint</em> of the reversed iterator is obtained
by providing <code>reverse_iterator</code>'s constructor with <code>begin()</code>: the
<em>begin point</em> of the normal iterator range.
<p>
The following little program illustrates the use of <code>StringPtr</code>'s
<code>RandomAccessIterator</code>:
        <pre>
    #include &lt;iostream&gt;
    #include &lt;algorithm&gt;
    #include "stringptr.h"
    using namespace std;

    int main(int argc, char **argv)
    {
        StringPtr sp;

        while (*argv)
            sp.push_back(new string(*argv++));

        sort(sp.begin(), sp.end());
        copy(sp.begin(), sp.end(), ostream_iterator&lt;string&gt;(cout, " "));

        cout &lt;&lt; "\n======\n";

        sort(sp.rbegin(), sp.rend());
        copy(sp.begin(), sp.end(), ostream_iterator&lt;string&gt;(cout, " "));

        cout &lt;&lt; endl;
    }
    /*
            when called as:
        a.out bravo mike charlie zulu quebec

            generated output:
        a.out bravo charlie mike quebec zulu
        ======
        zulu quebec mike charlie bravo a.out
    */
</pre>
    Although it is thus possible to construct a reverse iterator from a normal
iterator, the opposite does not hold true: it is not possible to
    <a name="an2784"></a>
initialize a normal iterator from a reverse iterator.
        <a name="an2785"></a>

    Let's assume we would like to process all lines stored in a
<code>vector&lt;string&gt; lines</code> up to any trailing empty lines (or lines only
containing blanks) it might contain. How would we proceed? One approach is to
start the processing from the first line in the vector, continuing until
the first of the trailing empty lines. However, once we encounter an empty
line it does of course not have to be the first line of the set of trailing
empty lines. In that case, we would like to use the following algorithm:
    <ul>
    <li> First, use
            <pre>
        rit = find_if(lines.rbegin(), lines.rend(), NonEmpty());
</pre>
        to obtain a <code>reverse_iterator rit</code> pointing to the last non-empty
        line.
    <li> Next, use
            <pre>
        for_each(lines.begin(), --rit, Process());
</pre>
        to process all lines up to the first empty line.
    </ul>
    However, we can't mix iterators and reverse iterators when using generic
algorithms. So how can we initialize the second iterator using the available
<code>reverse_iterator</code>? The solution is actually not very difficult, as an
iterator may be initialized by a pointer. The reverse iterator <code>rit</code> is not
a pointer, but <code>&amp;*(rit - 1)</code> or <code>&amp;*--rit</code> is. Thus, we can use
        <pre>
        for_each(lines.begin(), &amp;*--rit, Process());
</pre>
    to process all the lines up to the first of the set of trailing empty
lines. In general, if <code>rit</code> is a <code>reverse_iterator</code> pointing to some
element, but we need an <code>iterator</code> to point to that element, we may use
<code>&amp;*rit</code> to initialize the iterator. Here, the dereference operator is
applied to reach the element the reverse iterator refers to. Then the address
operator is applied to obtain its address.
<p>

<hr>
<ul>
    <li> <a href="cplusplus.html">Table of Contents</a>
    <li> <a href="cplusplus18.html">Previous Chapter</a>
    <li> <a href="cplusplus20.html">Next Chapter</a>
</ul>
<hr>
</body>
</html>
